INTERNATIONAL GONGRESS . Using these ideas, we can get the following.
Proposition 4.4. Let n=1,2,3,…n=1,2,3,…n=1,2,3,dotsn=1,2,3, \ldotsn=1,2,3,…. The following are equivalent over RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0 :
GPH2nGPH2nGPH_(2)^(n)\mathrm{GPH}_{2}^{n}GPH2n on NNN\mathbb{N}N : for any largeness notion LLL\mathbb{L}L, there exists a finite set F⊆NF⊆NF subeNF \subseteq \mathbb{N}F⊆N such that FFFFF is 1 -dense (n,2,L)(n,2,L)(n,2,L)(n, 2, \mathbb{L})(n,2,L).
To give a characterization of GPH, we consider the following variants of the infinite Ramsey theorem which was originally introduced by Flood [11].
We define two forms of the Ramsey-type weak Kónig's lemma, RWKLknRWKLknRWKL_(k)^(n)\mathrm{RWKL}_{k}^{n}RWKLkn and RWKLkn−RWKLkn−RWKL_(k)^(n-)\mathrm{RWKL}_{k}^{n-}RWKLkn−, as follows:
RWKLkn−RWKLkn−RWKL_(k)^(n-)\mathrm{RWKL}_{k}^{n-}RWKLkn− : for any infinite (n,k)(n,k)(n,k)(n, k)(n,k)-coloring tree TTTTT on NNN\mathbb{N}N, there exists an infinite homogeneous function for TTTTT ( n≥1n≥1n >= 1n \geq 1n≥1 and k≥2k≥2k >= 2k \geq 2k≥2 ),
RWKL∞n−≡∀kRWKLkn−,RWKL∞∞−≡∀nRWKL∞n−RWKL∞n−≡∀kRWKLkn−,RWKL∞∞−≡∀nRWKL∞n−RWKL_(oo)^(n-)-=AA kRWKL_(k)^(n-),RWKL_(oo)^(oo-)-=AA nRWKL_(oo)^(n-)\mathrm{RWKL}_{\infty}^{n-} \equiv \forall k \mathrm{RWKL}_{k}^{n-}, \mathrm{RWKL}_{\infty}^{\infty-} \equiv \forall n \mathrm{RWKL}_{\infty}^{n-}RWKL∞n−≡∀kRWKLkn−,RWKL∞∞−≡∀nRWKL∞n−,
RWKLknRWKLknRWKL_(k)^(n)\mathrm{RWKL}_{k}^{n}RWKLkn : for any infinite (n,k)(n,k)(n,k)(n, k)(n,k)-coloring tree TTTTT on NNN\mathbb{N}N, there exists a constant infinite homogeneous function for TTTTT ( n≥1n≥1n >= 1n \geq 1n≥1 and k≥2k≥2k >= 2k \geq 2k≥2 ),
RWKL∞n≡∀kRWKLkn,RWKL∞∞≡∀nRWKL∞nRWKL∞n≡∀kRWKLkn,RWKL∞∞≡∀nRWKL∞nRWKL_(oo)^(n)-=AA kRWKL_(k)^(n),RWKL_(oo)^(oo)-=AA nRWKL_(oo)^(n)\mathrm{RWKL}_{\infty}^{n} \equiv \forall k \mathrm{RWKL}_{k}^{n}, \mathrm{RWKL}_{\infty}^{\infty} \equiv \forall n \mathrm{RWKL}_{\infty}^{n}RWKL∞n≡∀kRWKLkn,RWKL∞∞≡∀nRWKL∞n.
Note that the original definition of Ramsey-type weak KÅ‘nig's lemma by Flood is our RWKL 2121_(2)^(1){ }_{2}^{1}21. 77^(7){ }^{7}7 Over RCA 00_(0)_{0}0, it is strictly in-between WKL and DNR (see [11,12]). Variants of Ramsey-type weak Kónig's lemma with homogeneous functions are introduced and studied by Bienvenu, Patey, and Shafer in [2] and the definition of RWKLkn−RWKLkn−RWKL_(k)^(n-)\mathrm{RWKL}_{k}^{n-}RWKLkn− is inspired by them.
Theorem 4.5. Let n≥1n≥1n >= 1n \geq 1n≥1 or n=∞n=∞n=oon=\inftyn=∞ and k≥2k≥2k >= 2k \geq 2k≥2 or k=∞k=∞k=ook=\inftyk=∞. The following are equivalent over RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0 :
Proof. It is enough to show the equivalence for the case n≥1n≥1n >= 1n \geq 1n≥1 and k≥2k≥2k >= 2k \geq 2k≥2. Equivalence 3↔43↔43harr43 \leftrightarrow 43↔4 is easy from the definition. If f:[N]<N→Nf:[N]<N→Nf:[N]^( < N)rarrNf:[\mathbb{N}]^{<\mathbb{N}} \rightarrow \mathbb{N}f:[N]<N→N is asymptotically stable, then L={F:∃G⊆L={F:∃G⊆L={F:EE G sube\mathbb{L}=\{F: \exists G \subseteqL={F:∃G⊆
7 The original name in [11] was "Ramsey-type Kónig's lemma", but "Ramsey-type weak Kónig's lemma" turned to be the standard name in the later works. F|G|>f(G)}F|G|>f(G)}F|G| > f(G)}F|G|>f(G)\}F|G|>f(G)} is a largeness notion, which implies 1→21→21rarr21 \rightarrow 21→2. Conversely, if LLL\mathbb{L}L is a largeness notion, then a function fffff defined as f(F)=min{|G|−1:G⊆F∧G∈L}∪{|F|}f(F)=min{|G|−1:G⊆F∧G∈L}∪{|F|}f(F)=min{|G|-1:G sube F^^G inL}uu{|F|}f(F)=\min \{|G|-1: G \subseteq F \wedge G \in \mathbb{L}\} \cup\{|F|\}f(F)=min{|G|−1:G⊆F∧G∈L}∪{|F|} is asymptotically stable and F∈L↔|F|>f(F)F∈L↔|F|>f(F)F inLharr|F| > f(F)F \in \mathbb{L} \leftrightarrow|F|>f(F)F∈L↔|F|>f(F). This implies 2→12→12rarr12 \rightarrow 12→1. Implication 3→13→13rarr13 \rightarrow 13→1 is a standard compactness argument which we have seen in Proposition 3.1. To show 1→31→31rarr31 \rightarrow 31→3, let TTTTT be an infinite (n,k)(n,k)(n,k)(n, k)(n,k)-coloring tree on NNN\mathbb{N}N with no infinite constant homogeneous function. Define LLL\mathbb{L}L as F∈LF∈LF inLF \in \mathbb{L}F∈L if there is no p∈Tp∈Tp in Tp \in Tp∈T such that ppppp is constant on [F]n[F]n[F]^(n)[F]^{n}[F]n. Then, one can check that LLL\mathbb{L}L is a largeness notion, and hence by 1 , there exists a finite set F0⊆NF0⊆NF_(0)subeNF_{0} \subseteq \mathbb{N}F0⊆N which is 1 -dense (n,k,L)(n,k,L)(n,k,L)(n, k, \mathbb{L})(n,k,L). Take some p∈Tp∈Tp in Tp \in Tp∈T so that dom(p)⊇[F0]ndomâ¡(p)⊇F0ndom(p)supe[F_(0)]^(n)\operatorname{dom}(p) \supseteq\left[F_{0}\right]^{n}domâ¡(p)⊇[F0]n, then there must exist H⊆F0H⊆F0H subeF_(0)H \subseteq F_{0}H⊆F0 such that H∈LH∈LH inLH \in \mathbb{L}H∈L and ppppp is constant on [H]n[H]n[H]^(n)[H]^{n}[H]n, which is a contradiction.
In case n=3,4,5,…n=3,4,5,…n=3,4,5,dotsn=3,4,5, \ldotsn=3,4,5,…, any of the statements in the above theorem is just equivalent to ACA0ACA0ACA_(0)\mathrm{ACA}_{0}ACA0, so we mostly interested in the case n=1n=1n=1n=1n=1 and 2 . On the other hand, unlike RT21RT21RT_(2)^(1)\mathrm{RT}_{2}^{1}RT21 or PH21PH21PH_(2)^(1)\mathrm{PH}_{2}^{1}PH21, the principle GPH21GPH21GPH_(2)^(1)\mathrm{GPH}_{2}^{1}GPH21 is still not trivial since RWKL21RWKL21RWKL_(2)^(1)\mathrm{RWKL}_{2}^{1}RWKL21 (which is equivalent to RWKL21−RWKL21−RWKL_(2)^(1-)\mathrm{RWKL}_{2}^{1-}RWKL21− ) is not provable within RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0. This may be interpreted as saying that the generalized version of the Paris-Harrington principle cannot be proved without using some compactness argument. In general, RWKLkn−RWKLkn−RWKL_(k)^(n-)\mathrm{RWKL}_{k}^{n-}RWKLkn− is easily implied by WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0, but we do not know whether it is strictly weaker than WKL over RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0 or not in case n≥2n≥2n >= 2n \geq 2n≥2.
4.3. Iterations of generalized PHPHPH\mathbf{P H}PH and correctness statements
The iterated version of GPH can be related to stronger correctness statements.
Theorem 4.6. Let k=2k=2k=2k=2k=2 or k=∞k=∞k=ook=\inftyk=∞. Then ItGPHk2ItGPHk2ItGPH_(k)^(2)\mathrm{ItGPH}_{k}^{2}ItGPHk2 is equivalent to rΠ21rÎ 21rPi_(2)^(1)\mathrm{r} \Pi_{2}^{1}rÎ 21-corr (WKL0+RTk2)WKL0+RTk2(WKL_(0)+RT_(k)^(2))\left(\mathrm{WKL}_{0}+\mathrm{RT}_{k}^{2}\right)(WKL0+RTk2) over WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0.
Over ACA0′ACA0′ACA_(0)^(')\mathrm{ACA}_{0}^{\prime}ACA0′, any Π21Î 21Pi_(2)^(1)\Pi_{2}^{1}Î 21-formula (of possibly nonstandard length) is equivalent to a
rΠ21rÎ 21rPi_(2)^(1)\mathrm{r} \Pi_{2}^{1}rÎ 21-formula, and thus rΠ21rÎ 21rPi_(2)^(1)\mathrm{r} \Pi_{2}^{1}rÎ 21-truth predicate is actually the truth predicate for all Π21Î 21Pi_(2)^(1)\Pi_{2}^{1}Î 21-formulas. Furthermore, It is known that rΠ21−corr(ACA0)rÎ 21−corrâ¡ACA0rPi_(2)^(1)-corr(ACA_(0))\mathrm{r} \Pi_{2}^{1}-\operatorname{corr}\left(\mathrm{ACA}_{0}\right)rÎ 21−corrâ¡(ACA0) is equivalent to ACA0′.8ACA0′.8ACA_(0)^(').^(8)\mathrm{ACA}_{0}^{\prime} .{ }^{8}ACA0′.8 So we simply write Π21−corr(T)Î 21−corrâ¡(T)Pi_(2)^(1)-corr(T)\Pi_{2}^{1}-\operatorname{corr}(T)Î 21−corrâ¡(T) for rΠ21−corr(T)rÎ 21−corrâ¡(T)rPi_(2)^(1)-corr(T)\mathrm{r} \Pi_{2}^{1}-\operatorname{corr}(T)rÎ 21−corrâ¡(T) if T⊇ACA0T⊇ACA0T supeACA_(0)T \supseteq \mathrm{ACA}_{0}T⊇ACA0.
Theorem 4.7. The following are equivalent over RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0 :
Theorem 4.8. Over RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0, ItGPH is equivalent to Π21Î 21Pi_(2)^(1)\Pi_{2}^{1}Î 21 - corr(ACA0′)corrâ¡ACA0′corr(ACA_(0)^('))\operatorname{corr}\left(\mathrm{ACA}_{0}^{\prime}\right)corrâ¡(ACA0′).
We will see the proofs of these theorems using indicators in the next section.
The strength of ItGPH22ItGPH22ItGPH_(2)^(2)\mathrm{ItGPH}_{2}^{2}ItGPH22 or ItGPH2ItGPH2ItGPH^(2)\mathrm{ItGPH}^{2}ItGPH2 is rather unclear. It is not difficult to check that RCA0+ItGPH22RCA0+ItGPH22RCA_(0)+ItGPH_(2)^(2)\mathrm{RCA}_{0}+\mathrm{ItGPH}_{2}^{2}RCA0+ItGPH22 implies RT2RT2RT^(2)\mathrm{RT}^{2}RT2 and WKL0+RT22+IΣ11WKL0+RT22+IΣ11WKL_(0)+RT_(2)^(2)+ISigma_(1)^(1)\mathrm{WKL}_{0}+\mathrm{RT}_{2}^{2}+I \Sigma_{1}^{1}WKL0+RT22+IΣ11 implies ItGPH 22^(2){ }^{2}2 as in the proof of Proposition 3.1. (Note that even ItGPH does not imply ∣Σ11∣Σ11∣Sigma_(1)^(1)\mid \Sigma_{1}^{1}∣Σ11 since IΣ11IΣ11ISigma_(1)^(1)I \Sigma_{1}^{1}IΣ11 is never implied from
any true Π21Î 21Pi_(2)^(1)\Pi_{2}^{1}Î 21-statement.) In particular, they are true in any ωωomega\omegaω-models of WKL0+RT22WKL0+RT22WKL_(0)+RT_(2)^(2)\mathrm{WKL}_{0}+\mathrm{RT}_{2}^{2}WKL0+RT22. Meanwhile, the following questions are still open.
Question 4.6. quad\quad 1. Is ItGPH22ItGPH22ItGPH_(2)^(2)\mathrm{ItGPH}_{2}^{2}ItGPH22 equivalent to RT2RT2RT^(2)\mathrm{RT}^{2}RT2 over WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0 ?
Does ACA0ACA0ACA_(0)\mathrm{ACA}_{0}ACA0 imply ItGPH 22^(2){ }^{2}2 or ItGPH22ItGPH22ItGPH_(2)^(2)\mathrm{ItGPH}_{2}^{2}ItGPH22 ?
5. INDICATORS AND CORRECTNESS STATEMENTS
The notion of indicators is introduced by Kirby and Paris [23,32] to show several independence results from PA, and its theory is organized systematically by Kaye [21]. The argument of indicators can connect first-order objects with second-order objects by means of nonstandard models. Recently, indicators have been used to calibrate the proof-theoretic strength of the infinite Ramsey theorem in the context of reverse mathematics [6,24,34,46][6,24,34,46][6,24,34,46][6,24,34,46][6,24,34,46].
5.1. Models of first- and second-order arithmetic
To introduce the argument of indicators, we first set up basic model theory of firstand second-order arithmetic. For the details, see [16,21,26,39][16,21,26,39][16,21,26,39][16,21,26,39][16,21,26,39]. A structure for L1L1L_(1)\mathscr{L}_{1}L1 is a 6-tuple M=(M;0M,1M,+M,×M,≤M)M=M;0M,1M,+M,×M,≤MM=(M;0^(M),1^(M),+^(M),xx^(M), <= ^(M))M=\left(M ; 0^{M}, 1^{M},+{ }^{M}, \times{ }^{M}, \leq^{M}\right)M=(M;0M,1M,+M,×M,≤M). (We often omit the superscript MMMMM if it is clear from the context.) An L1L1L_(1)\mathscr{L}_{1}L1-structure ℜ=(ℜ;0,1,+,×,≤)ℜ=(ℜ;0,1,+,×,≤)ℜ=(ℜ;0,1,+,xx, <= )\Re=(\Re ; 0,1,+, \times, \leq)ℜ=(ℜ;0,1,+,×,≤) where 0,1,+,×,≤0,1,+,×,≤0,1,+,xx, <=0,1,+, \times, \leq0,1,+,×,≤ are usual is called the standard model, and an L1L1L_(1)\mathscr{L}_{1}L1-structure is said to be nonstandard if it is not isomorphic to ℜℜℜ\Reℜ. When we consider an expanded language L1∪U→L1∪U→L_(1)uu vec(U)\mathscr{L}_{1} \cup \vec{U}L1∪U→ where U→=U1,…,UkU→=U1,…,Ukvec(U)=U_(1),dots,U_(k)\vec{U}=U_{1}, \ldots, U_{k}U→=U1,…,Uk are secondorder constants, an L1∪U→L1∪U→L_(1)uu vec(U)\mathscr{L}_{1} \cup \vec{U}L1∪U→-structure is a pair (M,U→M)M,U→M(M, vec(U)^(M))\left(M, \vec{U}^{M}\right)(M,U→M) where MMMMM is an L1L1L_(1)\mathscr{L}_{1}L1-structure and Ui⊆MUi⊆MU_(i)sube MU_{i} \subseteq MUi⊆M. We may consider NNN\mathbb{N}N as a special second-order constant which satisfies ∀xx∈N∀xx∈NAA xx inN\forall x x \in \mathbb{N}∀xx∈N, in other words, NM=MNM=MN^(M)=M\mathbb{N}^{M}=MNM=M for any MMMMM. For second-order arithmetic, we use Henkin semantics. A structure for L2L2L_(2)\mathscr{L}_{2}L2 is a pair (M,S)(M,S)(M,S)(M, S)(M,S) where MMMMM is an L1L1L_(1)\mathscr{L}_{1}L1-structure and S⊆P(M)S⊆P(M)S subeP(M)S \subseteq \mathcal{P}(M)S⊆P(M). Thus, any L1∪U→L1∪U→L_(1)uu vec(U)\mathscr{L}_{1} \cup \vec{U}L1∪U→-structure can be considered as an L2L2L_(2)\mathscr{L}_{2}L2-structure.
In our study, models of WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0 play central roles. Here are two important theorems.
Theorem 5.1 (Harrington, see Section IX. 2 of [39]).
For any countable model (M,S)⊨RCA0(M,S)⊨RCA0(M,S)|==RCA_(0)(M, S) \models \operatorname{RCA}_{0}(M,S)⊨RCA0, there exists S¯⊇SS¯⊇Sbar(S)supe S\bar{S} \supseteq SS¯⊇S such that (M,S¯)⊨(M,S¯)⊨(M, bar(S))|==(M, \bar{S}) \models(M,S¯)⊨ WKL. 99^(9){ }^{9}9
WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0 is Π11Î 11Pi_(1)^(1)\Pi_{1}^{1}Î 11-conservative over RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0.
9 Model (M,S)(M,S)(M,S)(M, S)(M,S) is said to be countable if both of MMMMM and SSSSS are countable.
Now we give the definition of indicators. Here, we slightly arrange the definition in [21] so as to fit better with second-order arithmetic.
Definition 5.1 (Indicators). Let U→=U1,…,UkU→=U1,…,Ukvec(U)=U_(1),dots,U_(k)\vec{U}=U_{1}, \ldots, U_{k}U→=U1,…,Uk be second-order constants, and let T⊇T⊇T supeT \supseteqT⊇ EFA be an L2L2L_(2)\mathscr{L}_{2}L2-theory.
Let MMMMM be a countable nonstandard model of EFA U→U→vec(U)\vec{U}U→. A Σ0U→Σ0U→Sigma_(0)^( vec(U))\Sigma_{0}^{\vec{U}}Σ0U→-definable function Y:[M]<M→MY:[M]<M→MY:[M]^( < M)rarr MY:[M]^{<M} \rightarrow MY:[M]<M→M is said to be an indicator for TTTTT on MMMMM if for each F,F′∈[M]<M,Y(F)≤maxF,Y(F)≤Y(F′)F,F′∈[M]<M,Y(F)≤maxF,Y(F)≤YF′F,F^(')in[M]^( < M),Y(F) <= max F,Y(F) <= Y(F^('))F, F^{\prime} \in[M]^{<M}, Y(F) \leq \max F, Y(F) \leq Y\left(F^{\prime}\right)F,F′∈[M]<M,Y(F)≤maxF,Y(F)≤Y(F′) if F⊆F′F⊆F′F subeF^(')F \subseteq F^{\prime}F⊆F′, and
(cut) Y(F)>mY(F)>mY(F) > mY(F)>mY(F)>m for any m∈Nm∈Nm inNm \in \mathfrak{N}m∈N if and only if there exists a cut I⊊eMI⊊eMI⊊eMI \subsetneq e MI⊊eM and
A Σ0U→Σ0U→Sigma_(0)^( vec(U))\Sigma_{0}^{\vec{U}}Σ0U→-formula Y(F,m)Y(F,m)Y(F,m)Y(F, m)Y(F,m) is said to be an indicator for TTTTT if for any countable nonstandard model M⊨EFAV→M⊨EFAV→M|==EFA^( vec(V))M \models \mathrm{EFA}^{\vec{V}}M⊨EFAV→ with U→⊆V→(U→U→⊆V→(U→vec(U)sube vec(V)( vec(U)\vec{U} \subseteq \vec{V}(\vec{U}U→⊆V→(U→ is a subtuple of V→V→vec(V)\vec{V}V→ ), YYYYY defines an indicator for TTTTT on MMMMM.
For a given indicator YYYYY, we define two statements " Y≥mY≥mY >= mY \geq mY≥m " and " YYYYY int ≥m≥m>= m\geq m≥m " as follows:
Y≥m≡∀X0(X0 is infinite →∃F⊆fin X0Y(F)≥m)Yint ≥m≡∀a∃bY([a,b)N)≥mY≥m≡∀X0X0 is infinite →∃F⊆fin X0Y(F)≥mYint ≥m≡∀a∃bY[a,b)N≥m{:[Y >= m-=AAX_(0)(X_(0)" is infinite "rarr EE Fsube_("fin ")X_(0)Y(F) >= m)],[Y^("int ") >= m-=AA a EE bY([a,b)_(N)) >= m]:}\begin{aligned}
& Y \geq m \equiv \forall X_{0}\left(X_{0} \text { is infinite } \rightarrow \exists F \subseteq_{\text {fin }} X_{0} Y(F) \geq m\right) \\
& Y^{\text {int }} \geq m \equiv \forall a \exists b Y\left([a, b)_{\mathbb{N}}\right) \geq m
\end{aligned}Y≥m≡∀X0(X0 is infinite →∃F⊆fin X0Y(F)≥m)Yint ≥m≡∀a∃bY([a,b)N)≥m
Note that Y≥mY≥mY >= mY \geq mY≥m is ar Π11Î 11Pi_(1)^(1)\Pi_{1}^{1}Î 11-statement while Yint≥mYint≥mY^(int) >= mY^{\mathrm{int}} \geq mYint≥m is a Π2Î 2Pi_(2)\Pi_{2}Î 2-statement.
Theorem 5.3. Define Σ0Σ0Sigma_(0)\Sigma_{0}Σ0-formulas YPHn(F,m),YPH(F,m)YPHn(F,m),YPH(F,m)Y_(PH^(n))(F,m),Y_(PH)(F,m)Y_{\mathrm{PH}^{n}}(F, m), Y_{\mathrm{PH}}(F, m)YPHn(F,m),YPH(F,m), and YItPHkn(F,m)YItPHkn(F,m)Y_(ItPH_(k)^(n))(F,m)Y_{\mathrm{ItPH}_{k}^{n}}(F, m)YItPHkn(F,m) as follows:
YPHn(F,m)↔m=max{k′≤maxF:FYPHn(F,m)↔m=maxk′≤maxF:FY_(PH^(n))(F,m)harr m=max{k^(') <= max F:F:}Y_{\mathrm{PH}^{n}}(F, m) \leftrightarrow m=\max \left\{k^{\prime} \leq \max F: F\right.YPHn(F,m)↔m=max{k′≤maxF:F is 1-dense (n,k′)}∪{0}(n=2,3,…)n,k′∪{0}(n=2,3,…){:(n,k^('))}uu{0}(n=2,3,dots)\left.\left(n, k^{\prime}\right)\right\} \cup\{0\}(n=2,3, \ldots)(n,k′)}∪{0}(n=2,3,…),
YPH(F,m)↔m=max{n′≤maxF:FYPH(F,m)↔m=maxn′≤maxF:FY_(PH)(F,m)harr m=max{n^(') <= max F:F:}Y_{\mathrm{PH}}(F, m) \leftrightarrow m=\max \left\{n^{\prime} \leq \max F: F\right.YPH(F,m)↔m=max{n′≤maxF:F is 1-dense (n′,2)}∪{0}n′,2∪{0}{:(n^('),2)}uu{0}\left.\left(n^{\prime}, 2\right)\right\} \cup\{0\}(n′,2)}∪{0},
YItPHkn(F,m)↔m=max{m′≤maxF:FYItPHkn(F,m)↔m=maxm′≤maxF:FY_(ItPH_(k)^(n))(F,m)harr m=max{m^(') <= max F:F:}Y_{\mathrm{ItPH}_{k}^{n}}(F, m) \leftrightarrow m=\max \left\{m^{\prime} \leq \max F: F\right.YItPHkn(F,m)↔m=max{m′≤maxF:F is m′m′m^(')m^{\prime}m′-dense (n,k)}∪{0}(n=2,3,…(n,k)∪{0}(n=2,3,…{:(n,k)}uu{0}(n=2,3,dots\left.(n, k)\right\} \cup\{0\}(n=2,3, \ldots(n,k)}∪{0}(n=2,3,… or n=∞n=∞n=oon=\inftyn=∞ and k=2,3,4,…k=2,3,4,…k=2,3,4,dotsk=2,3,4, \ldotsk=2,3,4,… or k=∞)k=∞)k=oo)k=\infty)k=∞).
Then, we have the following:
YPHnYPHnY_(PH^(n))Y_{\mathrm{PH}^{n}}YPHn is an indicator for RCA0+1Σn−10RCA0+1Σn−10RCA_(0)+1Sigma_(n-1)^(0)\mathrm{RCA}_{0}+1 \Sigma_{n-1}^{0}RCA0+1Σn−10.
YPHYPHY_(PH)Y_{\mathrm{PH}}YPH is an indicator for ACA0ACA0ACA_(0)\mathrm{ACA}_{0}ACA0.
YItPHknYItPHknY_(ItPH_(k)^(n))Y_{\mathrm{ItPH}_{k}^{n}}YItPHkn is an indicator for WKL0+RTknWKL0+RTknWKL_(0)+RT_(k)^(n)\mathrm{WKL}_{0}+\mathrm{RT}_{k}^{n}WKL0+RTkn.
In addition, these facts are provable within WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0.
Proof. For statements 1 and 2, one can reformulate the discussions of [21, SECTIoN 14.3]. Statement 3 is essentially due to Paris [32, EXAMPLE 2] (see also [6, THEOREM 1] and [34, LEMMA 3.2]). We sketch the proof for statement 3 for the case n=2,3,…n=2,3,…n=2,3,dotsn=2,3, \ldotsn=2,3,… and k=2,3,…k=2,3,…k=2,3,dotsk=2,3, \ldotsk=2,3,…
lows from Proposition 3.1 and overspill. For the left-to-right direction, let MMMMM be a countable nonstandard model of EFA U→U→vec(U)\vec{U}U→ and let F∈[M]<MF∈[M]<MF in[M]^( < M)F \in[M]^{<M}F∈[M]<M be mmmmm-dense (n,k)(n,k)(n,k)(n, k)(n,k) for any m∈ℜm∈ℜm inℜm \in \Rem∈ℜ. By overspill, take d∈M∖ℜd∈M∖ℜd in M\\ℜd \in M \backslash \Red∈M∖ℜ such that FFFFF is ddddd-dense (n,k)(n,k)(n,k)(n, k)(n,k). We will construct a countable decreasing sequence of MMMMM-finite sets {Fi}i∈ℜFii∈ℜ{F_(i)}_(i inℜ)\left\{F_{i}\right\}_{i \in \Re}{Fi}i∈ℜ such that FiFiF_(i)F_{i}Fi is (d−i)(d−i)(d-i)(d-i)(d−i)-dense (n,k)(n,k)(n,k)(n, k)(n,k) and
Finally, we construct {Fi}i∈ℜFii∈ℜ{F_(i)}_(i inℜ)\left\{F_{i}\right\}_{i \in \Re}{Fi}i∈ℜ. Since [M]<M[M]<M[M]^( < M)[M]^{<M}[M]<M is countable, it is enough to show:
(ii)' if p∈[M]<M,p:[F]n→kp∈[M]<M,p:[F]n→kp in[M]^( < M),p:[F]^(n)rarr kp \in[M]^{<M}, p:[F]^{n} \rightarrow kp∈[M]<M,p:[F]n→k and FFFFF is ℓ+1â„“+1â„“+1\ell+1â„“+1-dense (n,k)(n,k)(n,k)(n, k)(n,k) with ℓ≥1ℓ≥1â„“ >= 1\ell \geq 1ℓ≥1, then there exists F′⊆FF′⊆FF^(')sube FF^{\prime} \subseteq FF′⊆F which is ℓâ„“â„“\ellâ„“-dense (n,k)(n,k)(n,k)(n, k)(n,k) such that FFFFF is ppppp-homogeneous.
For the next theorem, we want to formalize model-theoretic arguments within second-order arithmetic. Within WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0, one can set up basic (countable) model theory for first-order logic, and then prove Gödel's completeness theorem [39, SECTIONS II. 8 AND IV.3]. Standard techniques for countable nonstandard models of arithmetic such as the compactness theorem, over/underspill, back and forth, recursive saturation and forcing are naturally formalizable once a countable model with a full evaluation function (truth definition) is provided. On the other hand, it is not possible in general to consider NNN\mathbb{N}N itself as a model of first-order arithmetic since its truth definition is too complicated, 1010^(10){ }^{10}10 hence it is not easy to guarantee that a family of true sentences are consistent. Still, we can deal with the consistency of Π2Î 2Pi_(2)\Pi_{2}Î 2-sentences as follows.
Lemma 5.4. RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0 proves the following. Let A→=A1,…,AkA→=A1,…,Akvec(A)=A_(1),dots,A_(k)\vec{A}=A_{1}, \ldots, A_{k}A→=A1,…,Ak be sets, and let ΓΓGamma\GammaΓ be a set of true Π2A→Î 2A→Pi_(2)^( vec(A))\Pi_{2}^{\vec{A}}Î 2A→-sentences. Then, ΓΓGamma\GammaΓ is consistent (with considering A→A→vec(A)\vec{A}A→ as second-order constants). 1111^(11){ }^{11}11 Proof. We work within RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0 and show that NNN\mathbb{N}N (together with A→A→vec(A)\vec{A}A→ ) is a weak model of ΓΓGamma\GammaΓ in the sense of [39, DEFINITION II.8.9]. It is enough to construct a function f:SΓ→2f:SΓ→2f:S^(Gamma)rarr2f: S^{\Gamma} \rightarrow 2f:SΓ→2 which satisfies Tarski's truth definition, where SΓSΓS^(Gamma)S^{\Gamma}SΓ is the set of all substitution instances of subformulas of ΓΓGamma\GammaΓ. Let S0ΓS0ΓS_(0)^(Gamma)S_{0}^{\Gamma}S0Γ be the set of all substitution instances of Σ0A→Σ0A→Sigma_(0)^( vec(A))\Sigma_{0}^{\vec{A}}Σ0A→-subformulas of ΓΓGamma\GammaΓ. Since there is a Π1A→−Î 1A→−Pi_(1)^( vec(A))-\Pi_{1}^{\vec{A}}-Î 1A→− formula which defines the truth of all Σ0A→Σ0A→Sigma_(0)^( vec(A))\Sigma_{0}^{\vec{A}}Σ0A→-formulas, one can take a function f:S0Γ→2f:S0Γ→2f:S_(0)^(Gamma)rarr2f: S_{0}^{\Gamma} \rightarrow 2f:S0Γ→2 which satisfies the truth definition. Then fffff can be expanded to SΓSΓS^(Gamma)S^{\Gamma}SΓ by putting the truth value 1 for all sentences in SΓ∖S0ΓSΓ∖S0ΓS^(Gamma)\\S_(0)^(Gamma)S^{\Gamma} \backslash S_{0}^{\Gamma}SΓ∖S0Γ. (They are Σ1A→Σ1A→Sigma_(1)^( vec(A))\Sigma_{1}^{\vec{A}}Σ1A→ or Π2A→Î 2A→Pi_(2)^( vec(A))\Pi_{2}^{\vec{A}}Î 2A→ and always true.)
Theorem 5.5. Let T⊇RCA0T⊇RCA0T supeRCA_(0)T \supseteq \mathrm{RCA}_{0}T⊇RCA0 be an L2L2L_(2)\mathscr{L}_{2}L2-theory, and let YYYYY be an indicator for TTTTT.
For any rΠ11rÎ 11rPi_(1)^(1)\mathrm{r} \Pi_{1}^{1}rÎ 11-sentence φ,T⊢φφ,T⊢φvarphi,T|--varphi\varphi, T \vdash \varphiφ,T⊢φ if and only if RCA0+{Y≥m:m∈N}⊢φRCA0+{Y≥m:m∈N}⊢φRCA_(0)+{Y >= m:m inN}|--varphi\mathrm{RCA}_{0}+\{Y \geq m: m \in \mathfrak{N}\} \vdash \varphiRCA0+{Y≥m:m∈N}⊢φ.
For any Π2Î 2Pi_(2)\Pi_{2}Î 2-sentence φ,T⊢φφ,T⊢φvarphi,T|--varphi\varphi, T \vdash \varphiφ,T⊢φ if and only if ∣Σ1+{Yint≥m:m∈ℜ}⊢φ.12∣Σ1+Yint≥m:m∈ℜ⊢φ.12∣Sigma_(1)+{Y^(int) >= m:m inℜ}|--varphi.^(12)\mid \Sigma_{1}+\left\{Y^{\mathrm{int}} \geq m: m \in \Re\right\} \vdash \varphi .{ }^{12}∣Σ1+{Yint≥m:m∈ℜ}⊢φ.12
If YYYYY is an indicator for TTTTT provably in WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0, we also have the following:
Over RCA0,rΠ11−corr(T)RCA0,rÎ 11−corrâ¡(T)RCA_(0),rPi_(1)^(1)-corr(T)\mathrm{RCA}_{0}, \mathrm{r} \Pi_{1}^{1}-\operatorname{corr}(T)RCA0,rÎ 11−corrâ¡(T) is equivalent to ∀mY≥m∀mY≥mAA mY >= m\forall m Y \geq m∀mY≥m.
Over ∣Σ1,Π2∣Σ1,Î 2∣Sigma_(1),Pi_(2)\mid \Sigma_{1}, \Pi_{2}∣Σ1,Î 2-corr( T)T{:T)\left.T\right)T) is equivalent to ∀mYint≥m∀mYint≥mAA mY^(int) >= m\forall m Y^{\mathrm{int}} \geq m∀mYint≥m.
Proof. We show statements 1 and 3. (Statements 2 and 4 can be shown similarly.)
For the left-to-right direction of statement 1 , it is enough to show that if
{∀x∃yθ(U,x,y)}∪RCA0∪{Y≥m:m∈ℜ}{∀x∃yθ(U,x,y)}∪RCA0∪{Y≥m:m∈ℜ}{AA x EE y theta(U,x,y)}uuRCA_(0)uu{Y >= m:m inℜ}\{\forall x \exists y \theta(U, x, y)\} \cup \mathrm{RCA}_{0} \cup\{Y \geq m: m \in \Re\}{∀x∃yθ(U,x,y)}∪RCA0∪{Y≥m:m∈ℜ}
is consistent with a second-order constant UUUUU and a Σ0UΣ0USigma_(0)^(U)\Sigma_{0}^{U}Σ0U-formula θθtheta\thetaθ, then
{∀x∃yθ(U,x,y)}∪T{∀x∃yθ(U,x,y)}∪T{AA x EE y theta(U,x,y)}uu T\{\forall x \exists y \theta(U, x, y)\} \cup T{∀x∃yθ(U,x,y)}∪T
is consistent. Let (M,S)(M,S)(M,S)(M, S)(M,S) be a countable nonstandard model of
{∀x∃yθ(U,x,y)}∪RCA0∪{Y≥m:m∈N}{∀x∃yθ(U,x,y)}∪RCA0∪{Y≥m:m∈N}{AA x EE y theta(U,x,y)}uuRCA_(0)uu{Y >= m:m inN}\{\forall x \exists y \theta(U, x, y)\} \cup \mathrm{RCA}_{0} \cup\{Y \geq m: m \in \mathfrak{N}\}{∀x∃yθ(U,x,y)}∪RCA0∪{Y≥m:m∈N}
Then there exists an infinite set AAAAA in (M,S)(M,S)(M,S)(M, S)(M,S) such that for any a,b∈Aa,b∈Aa,b in Aa, b \in Aa,b∈A with a<ba<ba < ba<ba<b, ∀x<a∃y<bθ(U,x,y)∀x<a∃y<bθ(U,x,y)AA x < a EE y < b theta(U,x,y)\forall x<a \exists y<b \theta(U, x, y)∀x<a∃y<bθ(U,x,y). By overspill, there exists an MMMMM-finite set F⊆AF⊆AF sube AF \subseteq AF⊆A with Y(F)≥mY(F)≥mY(F) >= mY(F) \geq mY(F)≥m
11 This lemma also follows from (the relativization of) the fact that IΣ1IΣ1ISigma_(1)I \Sigma_{1}IΣ1 is equivalent to Π3Î 3Pi_(3)\Pi_{3}Î 3-corr(EFA). See [1].
For the left-to-right direction of statement 3 , we first formalize the right-to-left direction of statement 1 within WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0. In other words, "for each m∈N,Y≥mm∈N,Y≥mm inN,Y >= mm \in \mathbb{N}, Y \geq mm∈N,Y≥m is provable in TTTTT ", is provable within WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0. Thus it is provable within RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0 by Theorem 5.1.2 since it is a Π20Î 20Pi_(2)^(0)\Pi_{2}^{0}Î 20-statement, and hence rΠ11rÎ 11rPi_(1)^(1)\mathrm{r} \Pi_{1}^{1}rÎ 11-corr (T)(T)(T)(T)(T) implies ∀mY≥m∀mY≥mAA mY >= m\forall m Y \geq m∀mY≥m.
For the right-to-left direction, again we first work within WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0. It is enough to show that if ∀x∃yθ(U,x,y)∀x∃yθ(U,x,y)AA x EE y theta(U,x,y)\forall x \exists y \theta(U, x, y)∀x∃yθ(U,x,y) holds for some set UUUUU and a Σ0UΣ0USigma_(0)^(U)\Sigma_{0}^{U}Σ0U-formula θθtheta\thetaθ, then {∀x∃yθ(U,x,y)}∪T{∀x∃yθ(U,x,y)}∪T{AA x EE y theta(U,x,y)}uu T\{\forall x \exists y \theta(U, x, y)\} \cup T{∀x∃yθ(U,x,y)}∪T is consistent. Take an infinite set AAAAA such that AAAAA is Δ1UΔ1UDelta_(1)^(U)\Delta_{1}^{U}Δ1U-definable and for any a,b∈Aa,b∈Aa,b in Aa, b \in Aa,b∈A with a<b,∀x<a∃y<bθ(U,x,y)a<b,∀x<a∃y<bθ(U,x,y)a < b,AA x < a EE y < b theta(U,x,y)a<b, \forall x<a \exists y<b \theta(U, x, y)a<b,∀x<a∃y<bθ(U,x,y). Then, by the assumption, for any m∈Nm∈Nm inNm \in \mathbb{N}m∈N, there exists a finite set F⊆AF⊆AF sube AF \subseteq AF⊆A such that Y(F)≥mY(F)≥mY(F) >= mY(F) \geq mY(F)≥m. Thus, by Lemma 5.4, a set of Π2UÎ 2UPi_(2)^(U)\Pi_{2}^{U}Î 2U-sentences Γ=EFAU∪{∀a∈F∀b∈F(a<b→∀x<a∃y<bθ(U,x,y))}∪{Y(F)≥m:m∈N}Γ=EFAU∪{∀a∈F∀b∈F(a<b→∀x<a∃y<bθ(U,x,y))}∪{Y(F)≥m:m∈N}Gamma=EFA^(U)uu{AA a in F AA b in F(a < b rarr AA x < a EE y < b theta(U,x,y))}uu{Y(F) >= m:m inN}\Gamma=\mathrm{EFA}^{U} \cup\{\forall a \in F \forall b \in F(a<b \rightarrow \forall x<a \exists y<b \theta(U, x, y))\} \cup\{Y(F) \geq m: m \in \mathbb{N}\}Γ=EFAU∪{∀a∈F∀b∈F(a<b→∀x<a∃y<bθ(U,x,y))}∪{Y(F)≥m:m∈N} is consistent (consider FFFFF as a new number constant). Take a countable nonstandard model of ΓΓGamma\GammaΓ and formalize the argument for the left-to-right direction of statement 1 , then we see that {∀x∃yθ(U,x,y)}∪T{∀x∃yθ(U,x,y)}∪T{AA x EE y theta(U,x,y)}uu T\{\forall x \exists y \theta(U, x, y)\} \cup T{∀x∃yθ(U,x,y)}∪T is consistent.
The above argument actually showed that for any set UUUUU, " ∀mY≥m∀mY≥mAA mY >= m\forall m Y \geq m∀mY≥m with respect to any infinite set A≤TU′′A≤TU′′A <= _(T)U^('')A \leq_{T} U^{\prime \prime}A≤TU′′ implies Σ2UΣ2USigma_(2)^(U)\Sigma_{2}^{U}Σ2U-corr (T)(T)(T)(T)(T). This is a Π11Î 11Pi_(1)^(1)\Pi_{1}^{1}Î 11-statement provable in WKL0WKL0WKL_(0)W K L_{0}WKL0, so it is also provable within RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0 by Theorem 5.1.2. Thus RCA0RCA0RCA_(0)\mathrm{RCA}_{0}RCA0 proves that ∀mY≥m∀mY≥mAA mY >= m\forall m Y \geq m∀mY≥m implies rΠ11−corr(T)rÎ 11−corrâ¡(T)rPi_(1)^(1)-corr(T)\mathrm{r} \Pi_{1}^{1}-\operatorname{corr}(T)rÎ 11−corrâ¡(T).
Theorems 5.3 and 5.5 directly connect PHPHPH\mathrm{PH}PH and the correctness statements, and Theorems 2.1 and 2.2 are direct consequences of them. They also imply conservation theorems. Indeed, Theorem 2.6.2 is a direct consequence of Theorems 5.3 and 5.5 plus Theorem 3.8.5 (see [25][25][25][25][25] ).
Proofs of Theorems 3.2-3.6. By definitions, PH¯n,PH¯PH¯n,PH¯bar(PH)^(n), bar(PH)\overline{\mathrm{PH}}^{n}, \overline{\mathrm{PH}}PH¯n,PH¯, and ItPH¯knItPH¯knIt bar(PH)_(k)^(n)\mathrm{It} \overline{\mathrm{PH}}_{k}^{n}ItPH¯kn are equivalent to
variants of PHPHPH\mathrm{PH}PH and corresponding rΠ11rÎ 11rPi_(1)^(1)\mathrm{r} \Pi_{1}^{1}rÎ 11-correctness statements (1↔3(1↔3(1harr3(1 \leftrightarrow 3(1↔3 and 2↔42↔42harr42 \leftrightarrow 42↔4 of Theorems 3.2 and 3.3,1↔23.3,1↔23.3,1harr23.3,1 \leftrightarrow 23.3,1↔2 of Theorem 3.4,1↔2↔33.4,1↔2↔33.4,1harr2harr33.4,1 \leftrightarrow 2 \leftrightarrow 33.4,1↔2↔3 of Theorem 3.5 and Theorem 3.6) follow from Theorems 5.3 and 5.5. Implications between variants of PHPHPH\mathrm{PH}PH and well-foundedness statements follow from Theorem 3.8 (see the paragraph below Theorem 3.8). Other implications can be shown as follows: 3→53→53rarr53 \rightarrow 53→5 of Theorem 3.3 and 2→32→32rarr32 \rightarrow 32→3 of Theorem 3.4 are implied from the formalization of the fact that RCA0+IΣn0RCA0+IΣn0RCA_(0)+ISigma_(n)^(0)\mathrm{RCA}_{0}+\mathrm{I} \Sigma_{n}^{0}RCA0+IΣn0 proves well-foundedness of ωnkωnkomega_(n)^(k)\omega_{n}^{k}ωnk for each k∈ℜk∈ℜk inℜk \in \Rek∈ℜ, and 3↔43↔43harr43 \leftrightarrow 43↔4 of Theorem 3.3 is implied from the formalization of the conservation result for WKL0+RT2WKL0+RT2WKL_(0)+RT^(2)\mathrm{WKL}_{0}+\mathrm{RT}^{2}WKL0+RT2 in [40].
5.3. Indicators corresponding to largeness notions
To obtain a characterization of rΠ21rÎ 21rPi_(2)^(1)\mathrm{r} \Pi_{2}^{1}rÎ 21-correctness, we modify Theorem 5.5 using indicators which can preserve largeness notions.
Given two finite sets F0={x0<⋯<xℓ−1}F0=x0<⋯<xℓ−1F_(0)={x_(0) < cdots < x_(â„“-1)}F_{0}=\left\{x_{0}<\cdots<x_{\ell-1}\right\}F0={x0<⋯<xℓ−1} and F1={x0′<⋯<xℓ′−1′}F1=x0′<⋯<xℓ′−1′F_(1)={x_(0)^(') < cdots < x_(â„“^(')-1)^(')}F_{1}=\left\{x_{0}^{\prime}<\cdots<x_{\ell^{\prime}-1}^{\prime}\right\}F1={x0′<⋯<xℓ′−1′}, define F0⊴F1F0⊴F1F_(0)⊴F_(1)F_{0} \unlhd F_{1}F0⊴F1 as ℓ≤ℓ′ℓ≤ℓ′ℓ <= â„“^(')\ell \leq \ell^{\prime}ℓ≤ℓ′ and xi≥xi′xi≥xi′x_(i) >= x_(i)^(')x_{i} \geq x_{i}^{\prime}xi≥xi′ for any i<ℓi<â„“i < â„“i<\elli<â„“. A prelargeness notion LLL\mathbb{L}L is said to be normal if F0∈LF0∈LF_(0)inLF_{0} \in \mathbb{L}F0∈L and F0⊴F1F0⊴F1F_(0)⊴F_(1)F_{0} \unlhd F_{1}F0⊴F1 implies F1∈LF1∈LF_(1)inLF_{1} \in \mathbb{L}F1∈L. It is not difficult to check that LωLωL_(omega)\mathbb{L}_{\omega}Lω is a normal largeness
notion. For a given prelargeness notion LLL\mathbb{L}L, put L+={F∈L:∀G⊆[0,maxF]N(G⊵F→L+=F∈L:∀G⊆[0,maxF]N(G⊵F→L^(+)={F inL:AA G sube[0,max F]_(N)(G⊵F rarr:}\mathbb{L}^{+}=\left\{F \in \mathbb{L}: \forall G \subseteq[0, \max F]_{\mathbb{N}}(G \unrhd F \rightarrow\right.L+={F∈L:∀G⊆[0,maxF]N(G⊵F→G∈L)}G∈L)}G inL)}G \in \mathbb{L})\}G∈L)}. Then L+L+L^(+)\mathbb{L}^{+}L+is a normal prelargeness notion.
Lemma 5.6. The following is provable within WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0. For any largeness notion L,L+L,L+L,L^(+)\mathbb{L}, \mathbb{L}^{+}L,L+is a largeness notion.
Proof. Assume that LLL\mathbb{L}L is a prelargeness notion and there exists an infinite set X={x0<X=x0<X={x_(0) < :}X=\left\{x_{0}<\right.X={x0<x1<⋯}x1<⋯{:x_(1) < cdots}\left.x_{1}<\cdots\right\}x1<⋯} such that no finite subset of XXXXX is a member of L+L+L^(+)\mathbb{L}^{+}L+. Define a tree T⊆N<NT⊆N<NT subeN < NT \subseteq \mathbb{N}<\mathbb{N}T⊆N<N as σ∈Tσ∈Tsigma in T\sigma \in Tσ∈T if and only if σσsigma\sigmaσ is strictly increasing, {σ(i):i<|σ|}⊵{xi:i<|σ|}{σ(i):i<|σ|}⊵xi:i<|σ|{sigma(i):i < |sigma|}⊵{x_(i):i < |sigma|}\{\sigma(i): i<|\sigma|\} \unrhd\left\{x_{i}: i<|\sigma|\right\}{σ(i):i<|σ|}⊵{xi:i<|σ|} and {σ(i):i<|σ|}∉L{σ(i):i<|σ|}∉L{sigma(i):i < |sigma|}!inL\{\sigma(i): i<|\sigma|\} \notin \mathbb{L}{σ(i):i<|σ|}∉L. Then, TTTTT is a bounded tree and TTTTT is infinite. Take a path h∈[T]h∈[T]h in[T]h \in[T]h∈[T], then Y={h(i):i∈N}Y={h(i):i∈N}Y={h(i):i inN}Y=\{h(i): i \in \mathbb{N}\}Y={h(i):i∈N} is an infinite set and any finite subset of YYYYY is not a member of LLL\mathbb{L}L.
Now we generalize the notion of semiregularity with a normal (pre)largeness notion and consider a variant of Theorem 5.5.
A Σ0U→Σ0U→Sigma_(0)^( vec(U))\Sigma_{0}^{\vec{U}}Σ0U→-formula YL≡Y(L,F,m)YL≡Y(L,F,m)Y^(L)-=Y(L,F,m)Y^{\mathbb{L}} \equiv Y(\mathbb{L}, F, m)YL≡Y(L,F,m) (where L∈U→L∈U→Lin vec(U)\mathbb{L} \in \vec{U}L∈U→ ) is said to be an LLL\mathbb{L}L-semiregular indicator for an L2L2L_(2)\mathscr{L}_{2}L2-theory TTTTT if for any countable nonstandard model M⊨EFAVM⊨EFAVM|==EFA^(V)M \models \mathrm{EFA}^{V}M⊨EFAV with U→⊆V→U→⊆V→vec(U)sube vec(V)\vec{U} \subseteq \vec{V}U→⊆V→ such that LLL\mathbb{L}L is a normal prelargeness notion in M,YLM,YLM,Y^(L)M, Y^{\mathbb{L}}M,YL defines an indicator for TTTTT on MMMMM but the condition (cut) replaced by
Theorem 5.7. Let T⊇WKL0T⊇WKL0T supeWKL_(0)T \supseteq \mathrm{WKL}_{0}T⊇WKL0 be an L2L2L_(2)\mathscr{L}_{2}L2-theory, and let YLYLY^(L)Y^{\mathbb{L}}YL be an LLL\mathbb{L}L-semiregular indicator for TTTTT provably in WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0. Then the following assertions are equivalent over WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0 :
For any LLL\mathbb{L}L, if LLL\mathbb{L}L is a normal largeness notion, then ∀mYL≥m∀mYL≥mAA mY^(L) >= m\forall m Y^{\mathbb{L}} \geq m∀mYL≥m.
Proof. Implication 1→21→21rarr21 \rightarrow 21→2 follows from the same discussion as the proof for Theorem 5.5. To show 2→12→12rarr12 \rightarrow 12→1, we reason within WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0 and show that, assuming statement 2 is true, if θ(U)θ(U)theta(U)\theta(U)θ(U) holds for some set UUUUU and an rΠ11rÎ 11rPi_(1)^(1)\mathrm{r} \Pi_{1}^{1}rÎ 11-formula θ(U)θ(U)theta(U)\theta(U)θ(U), then {θ(U)}∪T{θ(U)}∪T{theta(U)}uu T\{\theta(U)\} \cup T{θ(U)}∪T is consistent. By [34, PROPOSITION 2.5], take a Σ00Σ00Sigma_(0)^(0)\Sigma_{0}^{0}Σ00-formula η(G,F)η(G,F)eta(G,F)\eta(G, F)η(G,F) such that WKLWKLW_(KL)W_{K L}WKL proves
Theorem 5.8. Let n=2,3,4…n=2,3,4…n=2,3,4dotsn=2,3,4 \ldotsn=2,3,4… or n=∞n=∞n=oon=\inftyn=∞ and k=2,3,4,…k=2,3,4,…k=2,3,4,dotsk=2,3,4, \ldotsk=2,3,4,… or k=∞k=∞k=ook=\inftyk=∞. Define Σ0LΣ0LSigma_(0)^(L)\Sigma_{0}^{\mathbb{L}}Σ0L formula YItGPHknLYItGPHknLY_(ItGPH_(k)^(n))^(L)Y_{\mathrm{ItGPH}_{k}^{n}}^{\mathbb{L}}YItGPHknL as follows:
within WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0.
Proof. Essentially the same as the proof for Theorem 5.3.3. We additionally need to show the following (which is an analogous of (i)'):
Proofs of Theorems 4.6, 4.7, and 4.8. By Lemma 5.6, ItGPHknItGPHknItGPH_(k)^(n)\mathrm{ItGPH}_{k}^{n}ItGPHkn is equivalent to the statement
ACKNOWLEDGMENTS
It is a pleasure to thank Leszek Kołodziejczyk for careful reading of the manuscript and helpful discussions and comments, and to Kazuyuki Tanaka for helpful suggestions and advice.
FUNDING
This work is partially supported by JSPS KAKENHI grant number 19K03601.
REFERENCES
[1] L. Beklemishev, Reflection principles and provability algebras in formal arithmetic. Russian Math. Surveys 60 (2005).
[2] L. Bienvenu, L. Patey, and P. Shafer, On the logical strengths of partial solutions to mathematical problems. Trans. Lond. Math. Soc. 4 (2017), no. 1, 30-71.
[3] T. Bigorajska and H. Kotlarski, A partition theorem for ααalpha\alphaα-large sets. Fund. Math. 160 (1999), no. 1, 27-37.
[4] T. Bigorajska and H. Kotlarski, Some combinatorics involving ξξxi\xiξ-large sets. Fund. Math. 175 (2002), no. 2, 119-125.
[5] T. Bigorajska and H. Kotlarski, Partitioning ααalpha\alphaα-large sets: some lower bounds. Trans. Amer. Math. Soc. 358 (2006), no. 11, 4981-5001.
[6] A. Bovykin and A. Weiermann, The strength of infinitary Ramseyan principles can be accessed by their densities. Ann. Pure Appl. Logic 168 (2017), no. 9, 1700−17091700−17091700-17091700-17091700−1709.
[7] P. A. Cholak, C. G. Jockusch, and T. A. Slaman, On the strength of Ramsey's theorem for pairs. J. Symbolic Logic 66 (2001), no. 1, 1-15.
[8] C. T. Chong, T. A. Slaman, and Y. Yang, The metamathematics of Stable Ramsey's Theorem for Pairs. J. Amer. Math. Soc. 27 (2014), no. 3, 863-892.
[9] D. D. Dzhafarov, D. R. Hirschfeldt, and S. C. Reitzes, Reduction games, provability, and compactness. 2020, arXiv:2008.00907.
[10] M. Fiori Carones, L. A. Kołodziejczyk, T. L. Wong, and K. Yokoyama, An isomorphism theorem for models of weak Kônig's lemma without primitive recursion. 2021, arXiv:2112.10876.
[11] S. Flood, Reverse mathematics and a Ramsey-type Kónig's lemma. J. Symbolic Logic 77 (2012), no. 4, 1272-1280.
[12] S. Flood and H. Towsner, Separating principles below WKL WL0WL0WL_(0)\mathrm{WL}_{0}WL0 MLQ Math. Log. QQQQQ. 62 (2016), no. 6, 507-529.
[13] H. M. Friedman, K. McAloon, and S. G. Simpson, A finite combinatorial principle which is equivalent to the 1-consistency of predicative analysis. In Patras Logic Symposion (Patras, 1980), pp. 197-230, Stud. Logic Found. Math. 109, North-Holland, Amsterdam-New York, 1982.
[14] J. Gaspar and U. Kohlenbach, On Tao's "finitary" infinite pigeonhole principle. J. Symbolic Logic 75 (2010), no. 1, 355-371.
[15] R. L. Goodstein, On the restricted ordinal theorem. J. Symbolic Logic 9 (1944), 33-41.
[16] P. Hájek and P. Pudlák, Metamathematics of first-order arithmetic. Perspect. Math. Log., Springer, Berlin, 1998.
[17] D. R. Hirschfeldt, Slicing the truth. Lect. Notes Ser. 28, Institute for Mathematical Sciences, National University of Singapore, 2014.
[18] J. L. Hirst, Combinatorics in subsystems of second order arithmetic. Ph.D. thesis, The Pennsylvania State University, 1987.
[19] C. G. Jockusch, Ramsey's theorem and recursion theory. J. Symbolic Logic 37 (1972), no. 2, 268-280.
[20] A. Kanamori and K. McAloon, On Gödel incompleteness and finite combinatorics. Ann. Pure Appl. Logic 33 (1987), no. 1, 23-41.
[21] R. Kaye, Models of Peano arithmetic. Oxford University Press, 1991.
[22] J. Ketonen and R. Solovay, Rapidly growing Ramsey functions. Ann. of Math. (2) 113 (1981), no. 2, 267-314.
[23] L. A. S. Kirby and J. B. Paris, Initial segments of models of Peano's axioms. In Set theory and hierarchy theory V (Proc. Third Conf., Bierutowice, 1976), pp. 211-226, Lecture Notes in Math. 619, Springer, Berlin, 1977.
[24] L. A. Kołodziejczyk, T. L. Wong, and K. Yokoyama, Ramsey's theorem for pairs, collection, and proof size. 2021, arXiv:2005.06854v2.
[25] L. A. Kołodziejczyk and K. Yokoyama, Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs. Selecta Math. (N.S.) 26 (2020), no. 4, 56, 18pp18pp18pp18 \mathrm{pp}18pp.
[26] R. Kossak and J. H. Schmerl, The structure of models of Peano arithmetic. Oxford Logic Guides 50, Oxford University Press, Oxford, 2006.
[27] H. Kotlarski, B. Piekart, and A. Weiermann, More on lower bounds for partitioning ααalpha\alphaα-large sets. Ann. Pure Appl. Logic 147 (2007), no. 3, 113-126.
[28] J. Liu, RT 2 does not imply WKL . J. Symbolic Logic 77 (2012), no. 2, 609-620.
[29] K. McAloon, Paris-Harrington incompleteness and progressions of theories. In Recursion theory (Ithaca, NY, 1982), pp. 447-460, Proc. Sympos. Pure Math. 42, Amer. Math. Soc., Providence, RI, 1985.
[30] B. Monin and L. Patey, SRT22 does not imply RT22 in omega-models. 2019, arXiv:1905.08427v3.
[31] F. Pakhomov and J. Walsh, Reflection ranks and ordinal analysis. 2019, arXiv:1805.02095v2.
[32] J. B. Paris, Some independence results for Peano arithmetic. J. Symbolic Logic 43 (1978), no. 4, 725-731.
[33] J. Paris and L. Harrington, A mathematical incompleteness in Peano arithmetic. In Handbook of mathematical logic, edited by J. Barwise, pp. 1133-1142, Stud. Logic Found. Math. 90, North-Holland, Amsterdam, 1977.
[34] L. Patey and K. Yokoyama, The proof-theoretic strength of Ramsey's theorem for pairs and two colors. Adv. Math. 330 (2018), 1034-1070.
[35] F. Pelupessy, Phase transition results for three Ramsey-like theorems. Notre Dame J. Form. Log. 57 (2016), no. 2, 195-207.
[36] F. Pelupessy, On the "finitary" Ramsey's theorem. 2016, arXiv:1508.02013v7.
[37] D. Seetapun and T. A. Slaman, On the strength of Ramsey's theorem. Notre Dame J. Form. Log. 36 (1995), no. 4, 570-582.
[38] S. G. Simpson, Unprovable theorems and fast-growing functions. In Logic and combinatorics (Arcata, CA, 1985), pp. 359-394, Contemp. Math. 65, Amer. Math. Soc., Providence, RI, 1987.
[39] S. G. Simpson, Subsystems of second order arithmetic. Perspect. Math. Log., Springer, Berlin, 1999.
[40] T. A. Slaman and K. Yokoyama, The strength of Ramsey's theorem for pairs and arbitrarily many colors. J. Symbolic Logic 838383\mathbf{8 3}83 (2018), no. 4, 1610-1617.
[41] M. D. Smet and A. Weiermann, Partitioning ααalpha\alphaα-large sets for α<εωα<εωalpha < epsi_(omega)\alpha<\varepsilon_{\omega}α<εω. 2010, arXiv:1001.2437.
[42] K. Tanaka, The self-embedding theorem of WKL0WKL0WKL_(0)\mathrm{WKL}_{0}WKL0 and a non-standard method. Ann. Pure Appl. Logic 84 (1997), no. 1, 41-49.
[43] T. Tao, Soft analysis, hard analysis, and the finite convergence principle. http:// terrytao.wordpress.com, 2007, appeared in T. Tao, Structure and randomness: pages from year one of a mathematical blog. American Mathematical Society, 2008, 298pp298pp298pp298 \mathrm{pp}298pp.
[44] A. Weiermann, A classification of rapidly growing Ramsey functions. Proc. Amer. Math. Soc. 132 (2004), no. 2, 553-561.
[45] K. Yokoyama, Unpublished note.
[46] K. Yokoyama, On the strength of Ramsey's theorem without Σ1Σ1Sigma_(1)\Sigma_{1}Σ1-induction. MLQMLQMLQM L QMLQ Math. Log. Q. 59 (2013), no. 1-2, 108-111.
CONSTRAINT SATISFACTION PROBLEM: WHAT MAKES THE PROBLEM EASY
DMITRIY ZHUK
Abstract
The Constraint Satisfaction Problem is the problem of deciding whether there is an assignment to a set of variables subject to some specified constraints. Systems of linear equations, graph coloring, and many other combinatorial problems can be expressed as Constraint Satisfaction Problems for some constraint language. In 1993 it was conjectured that for any constraint language the problem is either solvable in polynomial time, or NPcomplete, and for many years this conjecture was the main open question in the area. After this conjecture was resolved in 2017, we finally can say what makes the problem hard and what makes the problem easy. In the first part of the paper, we give an elementary introduction to the area, explaining how the full classification appeared and why it is formulated in terms of polymorphisms. We discuss what makes the problem NP-hard, what makes the problem solvable by local consistency checking, and explain briefly the main idea of one of the two proofs of the conjecture. The second part of the paper is devoted to the extension of the CSP, called Quantified CSP, where we allow using both universal and existential quantifiers. Finally, we discuss briefly other variants of the CSP, as well as some open questions related to them.
Probably the main question in theoretical computer science is to understand why some computational problems are easy (solvable in polynomial time) while others are difficult (NP-hard, PSpace-hard, and so on). What is the difference between P and NP? Why a system of linear equations can be solved in polynomial time by the Gaussian elimination but we cannot check whether a graph is 3-colorable in polynomial time (if we believe that P≠NP)P≠NP)P!=NP)\mathrm{P} \neq \mathrm{NP})P≠NP). What is the principal difference between these two problems? To work on this question, first we would like to classify the problems by whether they are solvable in polynomial time (tractable) or NP-complete. Even for very simple decision problems, sometimes we do not know the answer.
For example, a system of linear equations in Z2Z2Z_(2)\mathbb{Z}_{2}Z2 can be solved by Gaussian elimination, but if we are allowed to add one linear equation with usual sum for integers then the problem becomes NP-complete [26]. Surprisingly, the complexity is not known if we can add one equation modulo 24 to a system of linear equations in Z2Z2Z_(2)\mathbb{Z}_{2}Z2 (variables are still from {0,1}){0,1}){0,1})\{0,1\}){0,1}) [17]. In the paper we give a formal definition to such problems and discuss why some of them can be solved in polynomial time, while others are NP-hard.
X={x1,…,xn}X=x1,…,xnX={x_(1),dots,x_(n)}\mathbf{X}=\left\{x_{1}, \ldots, x_{n}\right\}X={x1,…,xn} is a set of variables,
D={D1,…,Dn}D=D1,…,DnD={D_(1),dots,D_(n)}\mathbf{D}=\left\{D_{1}, \ldots, D_{n}\right\}D={D1,…,Dn} is a set of the respective domains,
C={C1,…,Cm}C=C1,…,CmC={C_(1),dots,C_(m)}\mathbf{C}=\left\{C_{1}, \ldots, C_{m}\right\}C={C1,…,Cm} is a set of constraints,
where each variable xixix_(i)x_{i}xi can take on values in the nonempty domain DiDiD_(i)D_{i}Di, every constraint Cj∈CCj∈CC_(j)inCC_{j} \in \mathbf{C}Cj∈C is a pair (tj,Rj)tj,Rj(t_(j),R_(j))\left(t_{j}, R_{j}\right)(tj,Rj) where tjtjt_(j)t_{j}tj is a tuple of variables of length mjmjm_(j)m_{j}mj, called the constraint scope, and RjRjR_(j)R_{j}Rj is an mjmjm_(j)m_{j}mj-ary relation on the corresponding domains, called the constraint relation.
To simplify the presentation, we assume that the domain of every variable is a finite set AAAAA. We also assume that all the relations are from a set ΓΓGamma\GammaΓ, which we call the constraint language. Then the Constraint Satisfaction Problem over a constraint language ΓΓGamma\GammaΓ, denoted CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ), is the following decision problem: given a conjunctive formula
where R1,…,Rs∈ΓR1,…,Rs∈ΓR_(1),dots,R_(s)in GammaR_{1}, \ldots, R_{s} \in \GammaR1,…,Rs∈Γ, and vi,j∈{x1,…,xn}vi,j∈x1,…,xnv_(i,j)in{x_(1),dots,x_(n)}v_{i, j} \in\left\{x_{1}, \ldots, x_{n}\right\}vi,j∈{x1,…,xn} for every i,ji,ji,ji, ji,j, decide whether this formula is satisfiable. Note that in the paper we do not distinguish between relations and predicates, and in the previous formula we write relations meaning predicates.
2.1. Examples
It is well known that many combinatorial problems can be expressed as CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) for some constraint language ΓΓGamma\GammaΓ. Moreover, for some ΓΓGamma\GammaΓ the corresponding decision problem can be solved in polynomial time; while for others it is NP-complete. It was conjectured that CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is either in PPP\mathrm{P}P or NP-complete [29]. Let us consider several examples.
System of linear equations. Let A={0,1}A={0,1}A={0,1}A=\{0,1\}A={0,1} and
i.e., ΓΓGamma\GammaΓ consists of all linear equations in the field Z2Z2Z_(2)\mathbb{Z}_{2}Z2. Then CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is equivalent to the problem of solving a system of linear equations, which is solvable by the Gaussian elimination in polynomial time, thus, CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is in PPP\mathrm{P}P.
Graph 2-coloring. To color a graph using two colors, we just need to choose a color of every vertex so that adjacent vertices have different colors. We assign a variable to each vertex, and encode the two colors with 0 and 1. For an edge between the iiiii th and jjjjj th vertices, we add the constraint xi≠xjxi≠xjx_(i)!=x_(j)x_{i} \neq x_{j}xi≠xj. For instance, the 5 -cycle is equivalent to the CSP instance
Hence, the problem of graph 2-coloring is equivalent to CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) for A={0,1}A={0,1}A={0,1}A=\{0,1\}A={0,1} and Γ={≠}Γ={≠}Gamma={!=}\Gamma=\{\neq\}Γ={≠}. This problem can be solved locally. We choose a color of some vertex, then we color their neighbors with a different color, and so on. Either we will color all the vertices, or we will find an odd cycle, which means that the graph is not colorable using two colors. Thus, this problem is solvable in polynomial time.
Graph 3-coloring. Similarly, the problem of coloring a graph using 3 colors is equivalent to CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) for A={0,1,2}A={0,1,2}A={0,1,2}A=\{0,1,2\}A={0,1,2} and Γ={≠}Γ={≠}Gamma={!=}\Gamma=\{\neq\}Γ={≠}. Unlike the graph 2-coloring, this problem is known to be NP-complete [1].
NAE-satisfability and 1IN3-satisfability. Suppose A={0,1}A={0,1}A={0,1}A=\{0,1\}A={0,1}. NAE is the ternary notall-equal relation, that is, NAE ={0,1}3∖{(0,0,0),(1,1,1)}={0,1}3∖{(0,0,0),(1,1,1)}={0,1}^(3)\\{(0,0,0),(1,1,1)}=\{0,1\}^{3} \backslash\{(0,0,0),(1,1,1)\}={0,1}3∖{(0,0,0),(1,1,1)}. 1IN3 is the ternary 1-in-3 relation, that is, 1IN3={(0,0,1),(0,1,0),(1,0,0)}1INâ¡3={(0,0,1),(0,1,0),(1,0,0)}1IN 3={(0,0,1),(0,1,0),(1,0,0)}1 \operatorname{IN} 3=\{(0,0,1),(0,1,0),(1,0,0)\}1INâ¡3={(0,0,1),(0,1,0),(1,0,0)}. As it is known [40], both CSP({NAE})CSPâ¡({NAE})CSP({NAE})\operatorname{CSP}(\{\mathrm{NAE}\})CSPâ¡({NAE}) and CSP({1IN3})CSPâ¡({1IN3})CSP({1IN3})\operatorname{CSP}(\{1 \mathrm{IN} 3\})CSPâ¡({1IN3}) are NP-complete.
The main goal of this paper is to explain why the first two examples are in PPP\mathrm{P}P, while the others are NP-hard.
2.2. Reduction from one language to another
To prove the hardness result, we usually reduce a problem to a known NP-hard problem. Let us show how we can go from one constraint language to another. CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) can be
viewed as the problem of evaluating a sentence
where all variables are existentially quantified. Hence, if we could express one language using conjunctions and existential quantifiers from another language, then we get a reduction from one CSP to another. Let us explain how it works on a concrete example.
Let NA1 ={0,1}3∖{(1,1,1)}={0,1}3∖{(1,1,1)}={0,1}^(3)\\{(1,1,1)}=\{0,1\}^{3} \backslash\{(1,1,1)\}={0,1}3∖{(1,1,1)}, that is, a ternary relation that holds whenever not all elements are 1. Let A={0,1},Γ1={NA1,≠}A={0,1},Γ1={NA1,≠}A={0,1},Gamma_(1)={NA1,!=}A=\{0,1\}, \Gamma_{1}=\{\mathrm{NA} 1, \neq\}A={0,1},Γ1={NA1,≠}, and Γ2={1IN3}Γ2={1IN3}Gamma_(2)={1IN3}\Gamma_{2}=\{1 \mathrm{IN} 3\}Γ2={1IN3}. Let us show that CSP(Γ1)CSPâ¡Î“1CSP(Gamma_(1))\operatorname{CSP}\left(\Gamma_{1}\right)CSPâ¡(Γ1) and CSP(Γ2)CSPâ¡Î“2CSP(Gamma_(2))\operatorname{CSP}\left(\Gamma_{2}\right)CSPâ¡(Γ2) are (polynomially) equivalent. We may check that
(2.2)(x≠y)=∃u∃v1IN3(x,y,u)∧1IN3(u,u,v)(2.2)(x≠y)=∃u∃v1INâ¡3(x,y,u)∧1INâ¡3(u,u,v){:(2.2)(x!=y)=EE u EE v1IN 3(x","y","u)^^1IN 3(u","u","v):}\begin{equation*}
(x \neq y)=\exists u \exists v 1 \operatorname{IN} 3(x, y, u) \wedge 1 \operatorname{IN} 3(u, u, v) \tag{2.2}
\end{equation*}(2.2)(x≠y)=∃u∃v1INâ¡3(x,y,u)∧1INâ¡3(u,u,v)
If fact, from IIN3(u,u,v)IINâ¡3(u,u,v)IIN 3(u,u,v)\operatorname{IIN} 3(u, u, v)IINâ¡3(u,u,v) we derive that u=0u=0u=0u=0u=0, hence x≠yx≠yx!=yx \neq yx≠y. Similarly, we have
If x=y=z=1x=y=z=1x=y=z=1x=y=z=1x=y=z=1, then x′=y′=z′=0x′=y′=z′=0x^(')=y^(')=z^(')=0x^{\prime}=y^{\prime}=z^{\prime}=0x′=y′=z′=0, which contradicts 1IN3(x′,y′,z′)1INâ¡3x′,y′,z′1IN 3(x^('),y^('),z^('))1 \operatorname{IN} 3\left(x^{\prime}, y^{\prime}, z^{\prime}\right)1INâ¡3(x′,y′,z′). In all other cases, we can find an appropriate assignment.
Any instance of CSP(Γ1)CSPâ¡Î“1CSP(Gamma_(1))\operatorname{CSP}\left(\Gamma_{1}\right)CSPâ¡(Γ1) can be reduced to an instance of CSP(Γ2)CSPâ¡Î“2CSP(Gamma_(2))\operatorname{CSP}\left(\Gamma_{2}\right)CSPâ¡(Γ2) in the following way. We replace each constraint (xi≠xj)xi≠xj(x_(i)!=x_(j))\left(x_{i} \neq x_{j}\right)(xi≠xj) by the right-hand side of (2.2) introducing two new variables. Also, we replace each constraint NA1 (xi,xj,xk)xi,xj,xk(x_(i),x_(j),x_(k))\left(x_{i}, x_{j}, x_{k}\right)(xi,xj,xk) by the right-hand side of (2.3) introducing six new variables. This reduction is obviously polynomial (and even log-space). Similarly, we have
which implies a polynomial reduction from CSP(Γ2)CSPâ¡Î“2CSP(Gamma_(2))\operatorname{CSP}\left(\Gamma_{2}\right)CSPâ¡(Γ2) to CSP(Γ1)CSPâ¡Î“1CSP(Gamma_(1))\operatorname{CSP}\left(\Gamma_{1}\right)CSPâ¡(Γ1).
Let us give a formal definition for the above reduction. A formula of the form ∃y1…∃ynΦ∃y1…∃ynΦEEy_(1)dots EEy_(n)Phi\exists y_{1} \ldots \exists y_{n} \Phi∃y1…∃ynΦ, where ΦΦPhi\PhiΦ is a conjunction of relations from ΓΓGamma\GammaΓ is called a positive primitive formula (pp-formula) over ΓΓGamma\GammaΓ. If R(x1,…,xn)=∃y1…∃ynΦRx1,…,xn=∃y1…∃ynΦR(x_(1),dots,x_(n))=EEy_(1)dots EEy_(n)PhiR\left(x_{1}, \ldots, x_{n}\right)=\exists y_{1} \ldots \exists y_{n} \PhiR(x1,…,xn)=∃y1…∃ynΦ, then we say that RRRRR is ppppppp ppp defined by this formula, and ∃y1…∃ynΦ∃y1…∃ynΦEEy_(1)dots EEy_(n)Phi\exists y_{1} \ldots \exists y_{n} \Phi∃y1…∃ynΦ is called its ppppppp ppp-definition.
Theorem 2.1 ([35]). Suppose Γ1Γ1Gamma_(1)\Gamma_{1}Γ1 and Γ2Γ2Gamma_(2)\Gamma_{2}Γ2 are finite constraint languages such that each relation from Γ1Γ1Gamma_(1)\Gamma_{1}Γ1 is pp-definable over Γ2Γ2Gamma_(2)\Gamma_{2}Γ2. Then CSP(Γ1)CSPâ¡Î“1CSP(Gamma_(1))\operatorname{CSP}\left(\Gamma_{1}\right)CSPâ¡(Γ1) is polynomial time reducible to CSP(Γ2)CSPâ¡Î“2CSP(Gamma_(2))\operatorname{CSP}\left(\Gamma_{2}\right)CSPâ¡(Γ2).
2.3. Polymorphisms as invariants
If we can pp-define a relation RRRRR from a constraint language ΓΓGamma\GammaΓ and CSP({R})CSPâ¡({R})CSP({R})\operatorname{CSP}(\{R\})CSPâ¡({R}) is NP-hard, then CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is also NP-hard. How to show that such a relation cannot be ppdefined? To prove that something cannot be done, we usually find some fundamental property (invariant) that is satisfied by anything we can obtain. For the relations, the operations play the role of invariants.
We say that an operation f:An→f:An→f:A^(n)rarrf: A^{n} \rightarrowf:An→ A preserves a relation RRRRR of arity mmmmm if for any tuples (a1,1,…,a1,m),…,(an,1,…,an,m)∈Ra1,1,…,a1,m,…,an,1,…,an,m∈R(a_(1,1),dots,a_(1,m)),dots,(a_(n,1),dots,a_(n,m))in R\left(a_{1,1}, \ldots, a_{1, m}\right), \ldots,\left(a_{n, 1}, \ldots, a_{n, m}\right) \in R(a1,1,…,a1,m),…,(an,1,…,an,m)∈R the tuple
is in RRRRR. In this case we also say that fffff is a polymorphism of RRRRR, and RRRRR is an invariant of fffff. We say that an operation preserves a set of relations ΓΓGamma\GammaΓ if it preserves every relation in ΓΓGamma\GammaΓ. In this case we also write fffff is a polymorphism of ΓΓGamma\GammaΓ or f∈Pol(Γ)f∈Polâ¡(Γ)f in Pol(Gamma)f \in \operatorname{Pol}(\Gamma)f∈Polâ¡(Γ). It can be easily checked that if fffff preserves ΓΓGamma\GammaΓ, then fffff preserves any relation RRRRR pp-definable from ΓΓGamma\GammaΓ. Moreover, we can show [15,31][15,31][15,31][15,31][15,31] that Pol(Γ1)⊆Pol(Γ2)Polâ¡Î“1⊆Polâ¡Î“2Pol(Gamma_(1))sube Pol(Gamma_(2))\operatorname{Pol}\left(\Gamma_{1}\right) \subseteq \operatorname{Pol}\left(\Gamma_{2}\right)Polâ¡(Γ1)⊆Polâ¡(Γ2) if and only if Γ2Γ2Gamma_(2)\Gamma_{2}Γ2 is pp-definable over Γ1Γ1Gamma_(1)\Gamma_{1}Γ1, which means that the complexity of CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) depends only on Pol(Γ)Polâ¡(Γ)Pol(Gamma)\operatorname{Pol}(\Gamma)Polâ¡(Γ).
Example 1. Let RRRRR be the linear order relation on {0,1,2}{0,1,2}{0,1,2}\{0,1,2\}{0,1,2}, i.e.,
that is, f(a1,…,an)≤f(b1,…,bn)fa1,…,an≤fb1,…,bnf(a_(1),dots,a_(n)) <= f(b_(1),dots,b_(n))f\left(a_{1}, \ldots, a_{n}\right) \leq f\left(b_{1}, \ldots, b_{n}\right)f(a1,…,an)≤f(b1,…,bn). In other words, fffff is monotonic. For instance, the operations max and min are monotonic. By the above observation, we know that any relation pp-definable from RRRRR is also preserved by min and max.
Example 2. Let A={0,1}A={0,1}A={0,1}A=\{0,1\}A={0,1}. Let us show that 1IN3 cannot be pp-defined from NA1 and x≤yx≤yx <= yx \leq yx≤y. We can check that the conjunction x∧yx∧yx^^yx \wedge yx∧y (an operation on {0,1}{0,1}{0,1}\{0,1\}{0,1} ) preserves both NA1 and x≤yx≤yx <= yx \leq yx≤y. However, x∧yx∧yx^^yx \wedge yx∧y does not preserve 1IN3 as we have
For more information on polymorphisms and how they can be used to study the complexity of the CSP, see [6].
2.4. Local consistency
The first step of almost any algorithm solving a CSP instance is checking local consistency. For instance, if a constraint forces a variable to be equal to 0 , then we could substitute 0 and remove this variable.
This instance is called 1 -consistent (also known as arc-consistent), if for any variable xxxxx any two constraints Ri(vi,1,…,vi,ni)Rivi,1,…,vi,niR_(i)(v_(i,1),dots,v_(i,n_(i)))R_{i}\left(v_{i, 1}, \ldots, v_{i, n_{i}}\right)Ri(vi,1,…,vi,ni) and Rj(vj,1,…,vj,nj)Rjvj,1,…,vj,njR_(j)(v_(j,1),dots,v_(j,n_(j)))R_{j}\left(v_{j, 1}, \ldots, v_{j, n_{j}}\right)Rj(vj,1,…,vj,nj) having this variable in the scope have the same projection onto this variable. This means that for every variable xxxxx there exists Dx⊆ADx⊆AD_(x)sube AD_{x} \subseteq ADx⊆A, called the domain of xxxxx, such that the projection of any constraint on xxxxx is DxDxD_(x)D_{x}Dx.
Sometimes we need a stronger consistency (similar to singleton-arc-consistency in [36]). We say that z1−C1−z2−⋯−Cl−1−zlz1−C1−z2−⋯−Cl−1−zlz_(1)-C_(1)-z_(2)-cdots-C_(l-1)-z_(l)z_{1}-C_{1}-z_{2}-\cdots-C_{l-1}-z_{l}z1−C1−z2−⋯−Cl−1−zl is a path in a CSP instance ddddd if zi,zi+1zi,zi+1z_(i),z_(i+1)z_{i}, z_{i+1}zi,zi+1 are in the scope of the constraint CiCiC_(i)C_{i}Ci for every i∈{1,2,…,l−1}i∈{1,2,…,l−1}i in{1,2,dots,l-1}i \in\{1,2, \ldots, l-1\}i∈{1,2,…,l−1}. We say that aaaaa path z1−C1−z2−⋯−Cl−1−zlz1−C1−z2−⋯−Cl−1−zlz_(1)-C_(1)-z_(2)-cdots-C_(l-1)-z_(l)z_{1}-C_{1}-z_{2}-\cdots-C_{l-1}-z_{l}z1−C1−z2−⋯−Cl−1−zl connects bbbbb and ccccc if there exist a1,a2,…,al∈Aa1,a2,…,al∈Aa_(1),a_(2),dots,a_(l)in Aa_{1}, a_{2}, \ldots, a_{l} \in Aa1,a2,…,al∈A such that a1=b,al=ca1=b,al=ca_(1)=b,a_(l)=ca_{1}=b, a_{l}=ca1=b,al=c, and the projection of each CiCiC_(i)C_{i}Ci onto zi,zi+1zi,zi+1z_(i),z_(i+1)z_{i}, z_{i+1}zi,zi+1 contains the tuple (ai,ai+1)ai,ai+1(a_(i),a_(i+1))\left(a_{i}, a_{i+1}\right)(ai,ai+1). A CSP instance ddddd is called cycle-consistent if it is 1-consistent and for every variable zzzzz and a∈Dza∈Dza inD_(z)a \in D_{z}a∈Dz any path starting and ending with zzzzz in ℓâ„“â„“\ellâ„“ connects aaaaa and aaaaa.
It is not hard to find a polynomial procedure making the instance 1-consistent or cycle-consistent. For 1-consistency, the idea is to find a variable where the consistency is violated, then reduce the domain DxDxD_(x)D_{x}Dx of this variable and reduce the corresponding relations. We repeat this while some constraints violate consistency. Finally, we either get a 1-consistent instance, or we get a contradiction (derive that Dx=∅Dx=∅D_(x)=O/D_{x}=\varnothingDx=∅ ). For cycle-consistency, we should go deeper. For every variable xxxxx and every value a∈Dxa∈Dxa inD_(x)a \in D_{x}a∈Dx, we reduce the domain of xxxxx to {a}{a}{a}\{a\}{a} and check whether the remaining instance can be made 1-consistent. If not, then xxxxx cannot be equal to aaaaa, and aaaaa can be excluded from the domain DxDxD_(x)D_{x}Dx.
Later we will show that in some cases 1-consistency and cycle-consistency are enough to solve a CSP instance, that is, any consistent instance has a solution. See [5, 36] for more information about local consistency conditions.
2.5. CSP over a 2-element domain
The complexity of CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) for each constraint language ΓΓGamma\GammaΓ on {0,1}{0,1}{0,1}\{0,1\}{0,1} was described in 1978 [40]. This classification can be formulated nicely using polymorphisms.
Theorem 2.2 ([34,40]). Suppose A={0,1},ΓA={0,1},ΓA={0,1},GammaA=\{0,1\}, \GammaA={0,1},Γ is a constraint language on AAAAA. Then CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is solvable in polynomial time if
(1) 0 preserves ΓΓGamma\GammaΓ, or
(2) 1 preserves ΓΓGamma\GammaΓ, or
(3) x∨yx∨yx vv yx \vee yx∨y preserves ΓΓGamma\GammaΓ, or
(4) x∧yx∧yx^^yx \wedge yx∧y preserves ΓΓGamma\GammaΓ, or
(5) xy∨yz∨xzxy∨yz∨xzxy vv yz vv xzx y \vee y z \vee x zxy∨yz∨xz preserves ΓΓGamma\GammaΓ, or
CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is NP-complete otherwise.
Let us consider each case and explain how the polymorphisms make the problem easy. Note that the cases (1) and (2), (3) and (4) are dual to each other, that is why we consider only one in each pair in detail.
000\mathbf{0}0 preserves ΓΓGamma\boldsymbol{\Gamma}Γ. This case is almost trivial. "The constant 0 preserves a relation R∈ΓR∈ΓR in GammaR \in \GammaR∈Γ " means that R(0,0,…,0)R(0,0,…,0)R(0,0,dots,0)R(0,0, \ldots, 0)R(0,0,…,0) holds. If 0 preserves all relations from ΓΓGamma\GammaΓ, then (0,0,…,0)(0,0,…,0)(0,0,dots,0)(0,0, \ldots, 0)(0,0,…,0) is always a solution of a CSPCSPCSP\operatorname{CSP}CSP instance, which makes the problem CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) trivial.
x∨yx∨yx vv y\boldsymbol{x} \vee \boldsymbol{y}x∨y preserves ΓΓGamma\GammaΓ. Let us show how to solve an instance of CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) if x∨y∈Pol(Γ)x∨y∈Polâ¡(Γ)x vv y in Pol(Gamma)x \vee y \in \operatorname{Pol}(\Gamma)x∨y∈Polâ¡(Γ). First, we make our instance 1-consistent. Then, unless we get a contradiction, every variable xxxxx has its domain DxDxD_(x)D_{x}Dx which is either {0}{0}{0}\{0\}{0}, or {1}{1}{1}\{1\}{1}, or {0,1}{0,1}{0,1}\{0,1\}{0,1}. We claim that if we send the variables with domain {0}{0}{0}\{0\}{0} to 0 , and the variables with the domain {1}{1}{1}\{1\}{1} and {0,1}{0,1}{0,1}\{0,1\}{0,1} to 1 , then we get a solution. In fact, if we apply x∨yx∨yx vv yx \vee yx∨y to all the tuples of some constraint, we obtain a tuple consistent with the solution. Thus, 1-consistency guarantees the existence of a solution in this case.
xy∨yz∨xzxy∨yz∨xzxy vv yz vv xz\boldsymbol{x} \boldsymbol{y} \vee \boldsymbol{y} z \vee \boldsymbol{x} zxy∨yz∨xz preserves ΓΓGamma\boldsymbol{\Gamma}Γ. The operation xy∨yz∨xzxy∨yz∨xzxy vv yz vv xzx y \vee y z \vee x zxy∨yz∨xz returns the most popular value and is known as a majority operation. It is not hard to check [2] that any relation preserved by a majority operation can be represented as a conjunction of binary relations, and we may assume that ΓΓGamma\GammaΓ consists of only binary relations. As it is shown in Section 2.8, for a 2-element domain this gives a polynomial algorithm for CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ). Additionally, we can show [36,47][36,47][36,47][36,47][36,47] that any cycle-consistent instance of CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) has a solution. Hence to solve an instance, it is sufficient to make it cycle-consistent, and unless we obtain an empty domain (contradiction) the instance has a solution.
x+y+zx+y+zx+y+z\boldsymbol{x}+\boldsymbol{y}+\boldsymbol{z}x+y+z preserves ΓΓGamma\boldsymbol{\Gamma}Γ. It is known (see Lemma 2.8) that x+y+zx+y+zx+y+zx+y+zx+y+z preserves a relation RRRRR if and only if the relation RRRRR can be represented as a conjunction of linear equations. Thus, CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is equivalent to the problem of solving of a system of linear equations in the field Z2Z2Z_(2)\mathbb{Z}_{2}Z2, which is tractable.
2.6. CSP solvable by local consistency checking
As we see in the previous section all tractable CSPs on a 2-element domain can be solved by two algorithms. The first algorithm just checks some local consistency (1-consistency, cycle-consistency) and, if a sufficient level of consistency achieved, we know that the instance has a solution. The second algorithm is the Gaussian elimination applied to a system of linear equations. In this section we discuss when the first algorithm is sufficient and why some instances can be solved by a local consistency checking, while others require something else.
To simplify the presentation in this section, we assume that all constant relations x=ax=ax=ax=ax=a are in the constraint language. In this case any polymorphism fffff of ΓΓGamma\GammaΓ is idempotent, that is, f(x,x,…,x)=xf(x,x,…,x)=xf(x,x,dots,x)=xf(x, x, \ldots, x)=xf(x,x,…,x)=x. This restriction does not affect the generality of the results because we can always consider the core of the constraint language and then add all constant relations
(see [34]). Consider the following system of linear equations in ZpZpZ_(p)\mathbb{Z}_{p}Zp :
If we calculate the sum of all equations, we will get 0=10=10=10=10=1, which means that the system does not have a solution. Nevertheless, we may check that the system is cycle-consistent, which means that the cycle-consistency does not guarantee the existence of a solution for linear equations. In fact, we can show that there does not exist a local consistency condition that guarantees the existence of a solution of a system of linear equations (see [5]).
As it was shown in [5,47][5,47][5,47][5,47][5,47] if CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) cannot be solved by cycle-consistency checking then we can express a linear equation modulo ppppp using ΓΓGamma\GammaΓ. Since our constraint language is on a domain AAAAA, we could not expect to pp-define the relation x1+x2=x3+x4(modp)x1+x2=x3+x4(modp)x_(1)+x_(2)=x_(3)+x_(4)(mod p)x_{1}+x_{2}=x_{3}+x_{4}(\bmod p)x1+x2=x3+x4(modp). Instead, we claim that there exist S⊆AS⊆AS sube AS \subseteq AS⊆A and a surjective mapping φ:A→Zpsφ:A→Zpsvarphi:A rarrZ_(p)^(s)\varphi: A \rightarrow \mathbb{Z}_{p}^{s}φ:A→Zps such that the relation
is pp-definable. This means that the linear equation is defined on some SSSSS modulo some equivalence relation defined by φφvarphi\varphiφ. To avoid such a transformation, we could introduce the notion of pp-constructability and say that x1+x2=x3+x4(modp)x1+x2=x3+x4(modp)x_(1)+x_(2)=x_(3)+x_(4)(mod p)x_{1}+x_{2}=x_{3}+x_{4}(\bmod p)x1+x2=x3+x4(modp) is pp-constructable from ΓΓGamma\GammaΓ. To keep everything simple, we do not define pp-constructability and use it informally hoping that the idea of this notion is clear from our example. For more details about pp-constructability, see [7].
If such a linear equation cannot be pp-defined (pp-constructed) then there should be some operation that preserves ΓΓGamma\GammaΓ but not the linear equation modulo ppppp. An operation fffff is called aaaaa Weak Near Unanimity Operation (WNU) if it satisfies the following identity:
It is not hard to check that an idempotent WNUWNUWNU\mathrm{WNU}WNU of arity ppppp does not preserve a nontrivial linear equation modulo ppppp (see Lemma 4.9 in [47]). Thus, the existence of an idempotent ppppp-ary WNU polymorphism of ΓΓGamma\GammaΓ guarantees that a linear equation modulo ppppp cannot be pppppp\mathrm{pp}pp defined (pp-constructed). That is why a relation satisfying (2.6) is called ppppp-WNU-blocker Hence, if ΓΓGamma\GammaΓ has WNU polymorphisms of all arities then no linear equations can appear. The following theorem confirms that nothing but linear equations could be an obstacle for the local consistency checking.
Theorem 2.3 ([47]). Suppose ΓΓGamma\GammaΓ is a constraint language containing all constant relations. The following conditions are equivalent:
(1) every cycle-consistent instance of CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) has a solution;
(2) ΓΓGamma\GammaΓ has a WNU polymorphisms of all arities n≥3n≥3n >= 3n \geq 3n≥3;
(3) there does not exist a ppppp-WNU-blocker pp-definable from ΓΓGamma\GammaΓ.
Thus, the fact that we cannot express (pp-define, pp-construct) a nontrivial linear equation makes the problem solvable by the cycle-consistency checking.
2.7. CSP Dichotomy Conjecture
In this subsection, we formulate a criterion for CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) to be solvable in polynomial time. This criterion is known as the CSP Dichotomy Conjecture, it was formulated almost 30 years ago [28,29] but was an open question until 2017 [19,20,42,44].
Theorem 2.4 ( [19,20,42,44])[19,20,42,44])[19,20,42,44])[19,20,42,44])[19,20,42,44]). Suppose ΓΓGamma\GammaΓ is a constraint language on a finite set AAAAA. Then
(1) CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is solvable in polynomial time if ΓΓGamma\GammaΓ is preserved by a WNUWNUWNUW N UWNU;
(2) CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is NP-complete otherwise.
We can check (see Lemma 4.8 in [47]) that a WNU operation does not preserve a WNU-blocker. Moreover, we have the following criterion.
Lemma 2.5 ([47]). A constraint language ΓΓGamma\GammaΓ containing all constant relations is preserved by a WNU if and only if there is no WNU-blocker pp-definable from ΓΓGamma\GammaΓ.
Thus, CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is solvable in polynomial time if and only if a WNU-blocker cannot be pp-defined. Hence, the fact that we cannot pp-construct the not-all-equal relation makes the problem easy, and a WNUWNUWNU\mathrm{WNU}WNU is an operation that guarantees that this relation cannot be pp-constructed.
2.8. How to solve CSP if pp-definable relations are simple
Below we discuss how the fact that only simple relations can be pp-defined from ΓΓGamma\GammaΓ can help to solve CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) in polynomial time. In this case we can calculate the sentence explicitly eliminating existential quantifiers one by one. I believe that a similar idea should work for any ΓΓGamma\GammaΓ preserved by a WNU, which will give us a simple algorithm for CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ).
CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) can be viewed as the following problem. Given a sentence
In general, Δn−1Δn−1Delta_(n-1)\Delta_{n-1}Δn−1 could be any relation of arity n−1n−1n-1n-1n−1, and even to write this relation we need |A|n−1|A|n−1|A|^(n-1)|A|^{n-1}|A|n−1 bits. Nevertheless, we believe that if CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is tractable then the relation Δn−1Δn−1Delta_(n-1)\Delta_{n-1}Δn−1 (or
the important part of it) has a compact representation and can be efficiently computed. Then we calculate Δn−2,Δn−3,…,Δ0Δn−2,Δn−3,…,Δ0Delta_(n-2),Delta_(n-3),dots,Delta_(0)\Delta_{n-2}, \Delta_{n-3}, \ldots, \Delta_{0}Δn−2,Δn−3,…,Δ0, where Δi−1(x1,…,xi−1)=∃xiΔi(x1,…,xi)Δi−1x1,…,xi−1=∃xiΔix1,…,xiDelta_(i-1)(x_(1),dots,x_(i-1))=EEx_(i)Delta_(i)(x_(1),dots,x_(i))\Delta_{i-1}\left(x_{1}, \ldots, x_{i-1}\right)=\exists x_{i} \Delta_{i}\left(x_{1}, \ldots, x_{i}\right)Δi−1(x1,…,xi−1)=∃xiΔi(x1,…,xi), and the value of Δ0Δ0Delta_(0)\Delta_{0}Δ0 is the answer we need.
The implication ⇒⇒=>\Rightarrow⇒ is obvious. To prove ⇐â‡lArr\Leftarrow⇠assume that the left-hand side does not hold. Then the conjunctive part does not hold on both (x1,…,xn−1,0)x1,…,xn−1,0(x_(1),dots,x_(n-1),0)\left(x_{1}, \ldots, x_{n-1}, 0\right)(x1,…,xn−1,0) and (x1,…,xn−1,1)x1,…,xn−1,1(x_(1),dots,x_(n-1),1)\left(x_{1}, \ldots, x_{n-1}, 1\right)(x1,…,xn−1,1). Hence, there exist iiiii and jjjjj such that Ri(vi,1,…,vi,ni)Rivi,1,…,vi,niR_(i)(v_(i,1),dots,v_(i,n_(i)))R_{i}\left(v_{i, 1}, \ldots, v_{i, n_{i}}\right)Ri(vi,1,…,vi,ni) does not hold on (x1,x2,…,xn−1,0)x1,x2,…,xn−1,0(x_(1),x_(2),dots,x_(n-1),0)\left(x_{1}, x_{2}, \ldots, x_{n-1}, 0\right)(x1,x2,…,xn−1,0) and Rj(vj,1,…,vj,nj)Rjvj,1,…,vj,njR_(j)(v_(j,1),dots,v_(j,n_(j)))R_{j}\left(v_{j, 1}, \ldots, v_{j, n_{j}}\right)Rj(vj,1,…,vj,nj) does not hold on (x1,x2,…,xn−1,1)x1,x2,…,xn−1,1(x_(1),x_(2),dots,x_(n-1),1)\left(x_{1}, x_{2}, \ldots, x_{n-1}, 1\right)(x1,x2,…,xn−1,1). Hence, the (i,j)(i,j)(i,j)(i, j)(i,j)-part of the righthand side does not hold.
There are two problems if we use (2.7) to solve the CSP. First, as we mentioned above, the relation Ri,j(…)=∃xnRi(vi,1,…,vi,ni)∧Rj(vj,1,…,vj,nj)Ri,j(…)=∃xnRivi,1,…,vi,ni∧Rjvj,1,…,vj,njR_(i,j)(dots)=EEx_(n)R_(i)(v_(i,1),dots,v_(i,n_(i)))^^R_(j)(v_(j,1),dots,v_(j,n_(j)))R_{i, j}(\ldots)=\exists x_{n} R_{i}\left(v_{i, 1}, \ldots, v_{i, n_{i}}\right) \wedge R_{j}\left(v_{j, 1}, \ldots, v_{j, n_{j}}\right)Ri,j(…)=∃xnRi(vi,1,…,vi,ni)∧Rj(vj,1,…,vj,nj) probably does not have a compact representation. Second, if we remove the quantifiers ∃xn,∃xn−1,…,∃x1∃xn,∃xn−1,…,∃x1EEx_(n),EEx_(n-1),dots,EEx_(1)\exists x_{n}, \exists x_{n-1}, \ldots, \exists x_{1}∃xn,∃xn−1,…,∃x1 one by one, potentially we could get an exponential number of relations in the formula. Let us show how these problem are solved for concrete examples on a 2-element domain.
2.9. System of linear equations in Z2Z2Z_(2)\mathbb{Z}_{2}Z2
Let A={0,1}A={0,1}A={0,1}A=\{0,1\}A={0,1} and let ΓΓGamma\GammaΓ consist of linear equations in Z2Z2Z_(2)\mathbb{Z}_{2}Z2. Suppose that for every iiiii we have
If ani=0ani=0a_(n)^(i)=0a_{n}^{i}=0ani=0 then the constraint Ri(vi,1,…,vi,ni)Rivi,1,…,vi,niR_(i)(v_(i,1),dots,v_(i,n_(i)))R_{i}\left(v_{i, 1}, \ldots, v_{i, n_{i}}\right)Ri(vi,1,…,vi,ni) does not depend on xnxnx_(n)x_{n}xn, so we keep it as it is when remove the quantifier. Hence, in every case we have a compact representation of Δn−1Δn−1Delta_(n-1)\Delta_{n-1}Δn−1. To avoid the exponential growth of the number of the constraints, we use the idea from the Gaussian elimination. Choose kkkkk such that ank=1ank=1a_(n)^(k)=1a_{n}^{k}=1ank=1, then calculate only Rk,1,…,Rk,sRk,1,…,Rk,sR_(k,1),dots,R_(k,s)R_{k, 1}, \ldots, R_{k, s}Rk,1,…,Rk,s and ignore all the other relations. Thus, in this case we have
Proceeding this way, we calculate Δn−2,Δn−3,…,Δ0Δn−2,Δn−3,…,Δ0Delta_(n-2),Delta_(n-3),dots,Delta_(0)\Delta_{n-2}, \Delta_{n-3}, \ldots, \Delta_{0}Δn−2,Δn−3,…,Δ0. Note that (2.8) holds not only for linear equations but whenever a variable xnxnx_(n)x_{n}xn is uniquely determined by the other variables in Rk(vk,1,…,vk,n1)Rkvk,1,…,vk,n1R_(k)(v_(k,1),dots,v_(k,n_(1)))R_{k}\left(v_{k, 1}, \ldots, v_{k, n_{1}}\right)Rk(vk,1,…,vk,n1).
2.10. 2-satisfability
Let A={0,1}A={0,1}A={0,1}A=\{0,1\}A={0,1} and let ΓΓGamma\GammaΓ consist of all binary relations. In this case Ri,jRi,jR_(i,j)R_{i, j}Ri,j is also binary, which means that we do not have a problem with a compact representation. Also, every time we eliminate a quantifier and caclulate ΔiΔiDelta_(i)\Delta_{i}Δi, we remove the repetitive constraints. Therefore, in each ΔiΔiDelta_(i)\Delta_{i}Δi we cannot have more than i⋅i⋅222iâ‹…iâ‹…222i*i*2^(2^(2))i \cdot i \cdot 2^{2^{2}}iâ‹…iâ‹…222 constraints because we have iiiii different variables and 2222222^(2^(2))2^{2^{2}}222 different binary relations on {0,1}{0,1}{0,1}\{0,1\}{0,1}.
As we see, the main question in both examples is the existence of a compact representation. In the first example we represent any relation as a conjunction of linear equations, in the second we represent as a conjunction of binary relations. We could ask when such a compact representation exists. Let sΓ(n)sΓ(n)s_(Gamma)(n)s_{\Gamma}(n)sΓ(n) be the number of pp-definable from ΓΓGamma\GammaΓ relations of arity nnnnn. If log2sΓ(n)log2â¡sΓ(n)log_(2)s_(Gamma)(n)\log _{2} s_{\Gamma}(n)log2â¡sΓ(n) grows exponentially then we need exponential space to encode relations of arity nnnnn and we cannot expect a compact representation. We say that ΓΓGamma\GammaΓ has few subpowers if log2sΓ(n)<p(n)log2â¡sΓ(n)<p(n)log_(2)s_(Gamma)(n) < p(n)\log _{2} s_{\Gamma}(n)<p(n)log2â¡sΓ(n)<p(n) for a polynomial p(n)p(n)p(n)p(n)p(n). It turns out that there is a simple criterion for the constraint language to have few subpowers. An operation ttttt is called an edge operation if it satisfies the following identities:
t(x,x,y,y,y,…,y,y)=yt(x,y,x,y,y,…,y,y)=yt(y,y,y,x,y,…,y,y)=yt(y,y,y,y,x,…,y,y)=y…t(y,y,y,y,y,…,x,y)=yt(y,y,y,y,y,…,y,x)=yt(x,x,y,y,y,…,y,y)=yt(x,y,x,y,y,…,y,y)=yt(y,y,y,x,y,…,y,y)=yt(y,y,y,y,x,…,y,y)=y…t(y,y,y,y,y,…,x,y)=yt(y,y,y,y,y,…,y,x)=y{:[t(x","x","y","y","y","dots","y","y)=y],[t(x","y","x","y","y","dots","y","y)=y],[t(y","y","y","x","y","dots","y","y)=y],[t(y","y","y","y","x","dots","y","y)=y],[dots],[t(y","y","y","y","y","dots","x","y)=y],[t(y","y","y","y","y","dots","y","x)=y]:}\begin{gathered}
t(x, x, y, y, y, \ldots, y, y)=y \\
t(x, y, x, y, y, \ldots, y, y)=y \\
t(y, y, y, x, y, \ldots, y, y)=y \\
t(y, y, y, y, x, \ldots, y, y)=y \\
\ldots \\
t(y, y, y, y, y, \ldots, x, y)=y \\
t(y, y, y, y, y, \ldots, y, x)=y
\end{gathered}t(x,x,y,y,y,…,y,y)=yt(x,y,x,y,y,…,y,y)=yt(y,y,y,x,y,…,y,y)=yt(y,y,y,y,x,…,y,y)=y…t(y,y,y,y,y,…,x,y)=yt(y,y,y,y,y,…,y,x)=y
Theorem 2.6 ([9]). A constraint language ΓΓGamma\GammaΓ containing all constant relations has few subpowers if and only if it has an edge polymorphism.
We can show that if ΓΓGamma\GammaΓ has few subpowers then the pp-definable relations have a natural compact representation, which gives a polynomial algorithm for CSP(Г)CSPâ¡(Г)CSP(Г)\operatorname{CSP}(Г)ГCSPâ¡(Г) [33]. Note that two examples of an edge operation were given earlier in this paper. The first example is a majority operation satisfying m(y,y,x)=m(y,x,y)=m(x,y,y)=ym(y,y,x)=m(y,x,y)=m(x,y,y)=ym(y,y,x)=m(y,x,y)=m(x,y,y)=ym(y, y, x)=m(y, x, y)=m(x, y, y)=ym(y,y,x)=m(y,x,y)=m(x,y,y)=y. By adding 3 dummy variables in the beginning, we get the required properties of an edge operation. Another example is x+y+zx+y+zx+y+zx+y+zx+y+z on {0,1}{0,1}{0,1}\{0,1\}{0,1}. By adding dummy variables at the end, we can easily satisfy all the identities. Very roughly speaking, any few subpowers case is just a combination (probably very complicated) of the majority case and the linear case.
2.11. Strong subuniverses and a proof of the CSP Dichotomy Conjecture
In this subsection, we consider another simple idea that can solve the CSP in polynomial time. This idea is one of the two main ingredients of the proof of the CSP Dichotomy Conjecture in [42,44][42,44][42,44][42,44][42,44].
Assume that for every variable xxxxx whose domain is Dx,|Dx|>1Dx,Dx>1D_(x),|D_(x)| > 1D_{x},\left|D_{x}\right|>1Dx,|Dx|>1, we can choose a subset Bx⊊DxBx⊊DxB_(x)⊊D_(x)B_{x} \subsetneq D_{x}Bx⊊Dx such that if the instance has a solution, then it has a solution with x∈Bxx∈Bxx inB_(x)x \in B_{x}x∈Bx.
In this case we can reduce the domains iteratively until the moment when each domain has exactly one element, which usually gives us a solution.
As we saw in Section 2.5, if ΓΓGamma\GammaΓ is preserved by x∨yx∨yx vv yx \vee yx∨y and the instance is 1-consistent then we can safely reduce the domain of a variable to {1}{1}{1}\{1\}{1}. Similarly, if ΓΓGamma\GammaΓ is preserved by the majority operation xy∨yz∨xzxy∨yz∨xzxy vv yz vv xzx y \vee y z \vee x zxy∨yz∨xz and the instance is cycle-consistent, then we can safely reduce the domain {0,1}{0,1}{0,1}\{0,1\}{0,1} to {0}{0}{0}\{0\}{0} and {1}{1}{1}\{1\}{1} [47]. It turns out that this idea can be generalized for any constraint language preserved by a WNU operation.
A unary relation B⊆AB⊆AB sube AB \subseteq AB⊆A is called a subuniverse if BBBBB is pp-definable over ΓΓGamma\GammaΓ. It can be easily checked that all the domains DxDxD_(x)D_{x}Dx that appear while checking consistency (see Section 2.4) are subuniverses. Let us define three types of strong subuniverses:
Binary absorbing subuniverse. We say that B′B′B^(')B^{\prime}B′ is a binary absorbing subuniverse of BBBBB if there exists a binary operation f∈Pol(Γ)f∈Polâ¡(Γ)f in Pol(Gamma)f \in \operatorname{Pol}(\Gamma)f∈Polâ¡(Γ) such that f(B′,B)⊆B′fB′,B⊆B′f(B^('),B)subeB^(')f\left(B^{\prime}, B\right) \subseteq B^{\prime}f(B′,B)⊆B′ and f(B,B′)⊆B′fB,B′⊆B′f(B,B^('))subeB^(')f\left(B, B^{\prime}\right) \subseteq B^{\prime}f(B,B′)⊆B′. For example, if the operation x∨yx∨yx vv yx \vee yx∨y preserves ΓΓGamma\GammaΓ then {1}{1}{1}\{1\}{1} is a binary absorbing subuniverse of {0,1}{0,1}{0,1}\{0,1\}{0,1} and x∨yx∨yx vv yx \vee yx∨y is a binary absorbing operation.
Ternary absorbing subuniverse. We say that B′B′B^(')B^{\prime}B′ is a ternary absorbing subuniverse of BBBBB if there exists a ternary operation f∈Pol(Γ)f∈Polâ¡(Γ)f in Pol(Gamma)f \in \operatorname{Pol}(\Gamma)f∈Polâ¡(Γ) such that f(B′,B′,B)⊆B′,f(B′,B,B′)⊆B′fB′,B′,B⊆B′,fB′,B,B′⊆B′f(B^('),B^('),B)subeB^('),f(B^('),B,B^('))subeB^(')f\left(B^{\prime}, B^{\prime}, B\right) \subseteq B^{\prime}, f\left(B^{\prime}, B, B^{\prime}\right) \subseteq B^{\prime}f(B′,B′,B)⊆B′,f(B′,B,B′)⊆B′, and f(B,B′,B′)⊆B′fB,B′,B′⊆B′f(B,B^('),B^('))subeB^(')f\left(B, B^{\prime}, B^{\prime}\right) \subseteq B^{\prime}f(B,B′,B′)⊆B′. For example, if the majority operation xy∨yz∨xzxy∨yz∨xzxy vv yz vv xzx y \vee y z \vee x zxy∨yz∨xz preserves ΓΓGamma\GammaΓ, then both {0}{0}{0}\{0\}{0} and {1}{1}{1}\{1\}{1} are ternary absorbing subuniverses of {0,1}{0,1}{0,1}\{0,1\}{0,1}. Since we can always add a dummy variable to a binary absorbing operation, any binary absorbing subuniverse is also a ternary absorbing subuniverse.
To define the last type of strong subalgebras we need some understanding of the Universal Algebra. We do not think a concrete definition is important here, that is why if a reader thinks the definition is too complicated, we recommend to skip it and think about the last type as something similar to the first two.
PC subuniverse. A set FFFFF of operations is called Polynomially Complete (PC) if any operation can be derived from FFFFF and constants using composition. We say that B′B′B^(')B^{\prime}B′ is a PC subuniverse of BBBBB if there exists a pp-definable equivalence relation σ⊆B×Bσ⊆B×Bsigma sube B xx B\sigma \subseteq B \times Bσ⊆B×B such that Pol(Γ)/σPolâ¡(Γ)/σPol(Gamma)//sigma\operatorname{Pol}(\Gamma) / \sigmaPolâ¡(Γ)/σ is PCPCPC\mathrm{PC}PC.
A subset B′B′B^(')B^{\prime}B′ of BBBBB is called a strong subuniverse if B′B′B^(')B^{\prime}B′ is a ternary absorbing subuniverse or a PC subuniverse.
Theorem 2.7 ([47]). Suppose ΓΓGamma\GammaΓ contains all constant relations and is preserved by a WNU operation, B⊆AB⊆AB sube AB \subseteq AB⊆A is a subuniverse. Then
(1) there exists a strong subuniverse B′⊊BB′⊊BB^(')⊊BB^{\prime} \subsetneq BB′⊊B, or
(2) there exists a pp-definable nontrivial equivalence relation σσsigma\sigmaσ on BBBBB and f∈Pol(Γ)f∈Polâ¡(Γ)f in Pol(Gamma)f \in \operatorname{Pol}(\Gamma)f∈Polâ¡(Γ) such that (B;f)/σ≅(Zpk;x−y+z)(B;f)/σ≅Zpk;x−y+z(B;f)//sigma~=(Z_(p)^(k);x-y+z)(B ; f) / \sigma \cong\left(\mathbb{Z}_{p}^{k} ; x-y+z\right)(B;f)/σ≅(Zpk;x−y+z).
As it follows from the next lemma, the second condition implies that any ppdefinable relation (modulo σσsigma\sigmaσ ) can be viewed as a system of linear equations in a field.
Lemma 2.8 ([32]). Suppose R⊆ZpnR⊆ZpnR subeZ_(p)^(n)R \subseteq \mathbb{Z}_{p}^{n}R⊆Zpn preserved by x−y+zx−y+zx-y+zx-y+zx−y+z. Then RRRRR can be represented as a conjunction of relations of the form a1x1+⋯+anxn=a0(modp)a1x1+⋯+anxn=a0(modp)a_(1)x_(1)+cdots+a_(n)x_(n)=a_(0)(mod p)a_{1} x_{1}+\cdots+a_{n} x_{n}=a_{0}(\bmod p)a1x1+⋯+anxn=a0(modp).
For CSPs solvable by the local consistency checking, strong subuniverses have the following property.
Theorem 2.9 ([47]). Suppose
(1) ΓΓGamma\GammaΓ is a constraint language containing all constant relations;
(2) ΓΓGamma\GammaΓ is preserved by a WNUWNUWNUW N UWNU of each arity n≥3n≥3n >= 3n \geq 3n≥3;
(3) ddddd is a cycle-consistent instance of CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ);
(4) DxDxD_(x)D_{x}Dx is the domain of a variable xxxxx;
(5) BBBBB is a strong subalgebra of DxDxD_(x)D_{x}Dx.
Then & has a solution with x∈Bx∈Bx in Bx \in Bx∈B.
Thus, strong subuniverses have the required property that we cannot loose all the solutions when we restrict a variable to it. As it was proved in [44], a similar theorem holds for any constraint language preserved by a WNU operation (with additional consistency conditions on the instance). We skip this result because it would require too many additional definitions.
As we see from Theorem 2.7, for every domain DxDxD_(x)D_{x}Dx either we have a strong subuniverse and can reduce the domain of some variable, or, modulo some equivalence relation, we have a system of linear equations in a field. If ΓΓGamma\GammaΓ has a WNU polymorphism of each arity n≥3n≥3n >= 3n \geq 3n≥3, then we always have the first case; hence, we can iteratively reduce the domains until the moment when all the domains have just one element, which gives us a solution. That is why any cycle-consistent instance in this situation has a solution. If we always have the second case then this situation is similar to a system of linear equations, but different linear equations can be mixed which makes it impossible to apply usual Gaussian elimination. Nevertheless, the few subpowers algorithm solves the problem [33].
For many years the main obstacle was that these two situations can be mixed and at the moment we do not know an elegant way how to split them. Nevertheless, the general algorithm for tractable CSP presented in [44] is just a smart combination of these two ideas:
if there exists a strong subalgebra, reduce
if there exists a system of linear equations, solve it.
For more information about this approach as well as its connection with the second general algorithm see [3][3][3][3][3].
2.12. Conclusions
Even though we still do not have a simple algorithm that solves all tractable Constraint Satisfaction Problems, we understand what makes the problem hard, and what makes
the problem easy. First, we know that in all the hard cases we can pp-construct (pp-define) the not-all-equal relation, which means that all the NP-hard cases have the same nature. Second, if the CSP is not solvable locally then we can pp-construct (pp-define) a linear equation in a field. Moreover, any domain of a tractable CSP either has a strong subalgebra and we can (almost) safely reduce the domain, or there exists a system of linear equations on this domain. This implies that any tractable CSP can be solved by a smart combination of the Gaussian elimination and local consistency checking, and emphasizes the exclusive role of the linear case in Universal Algebra and Computational Complexity.
Note that both CSP algorithms in [20,44] depend exponentially on the size of the domain, and we could ask whether there exists a universal polynomial algorithm that works for any constraint language ΓΓGamma\GammaΓ admitting a WNU polymorphism.
Problem 1. Does there exist a polynomial algorithm for the following decision problem: given a conjunctive formula R1(v1,1,…,v1,n1)∧⋯∧Rs(vs,1,…,vs,ns)R1v1,1,…,v1,n1∧⋯∧Rsvs,1,…,vs,nsR_(1)(v_(1,1),dots,v_(1,n_(1)))^^cdots^^R_(s)(v_(s,1),dots,v_(s,n_(s)))R_{1}\left(v_{1,1}, \ldots, v_{1, n_{1}}\right) \wedge \cdots \wedge R_{s}\left(v_{s, 1}, \ldots, v_{s, n_{s}}\right)R1(v1,1,…,v1,n1)∧⋯∧Rs(vs,1,…,vs,ns), where all relations R1,…,RsR1,…,RsR_(1),dots,R_(s)R_{1}, \ldots, R_{s}R1,…,Rs are preserved by a WNU, decide whether this formula is satisfiable.
If the domain is fixed then the above problem can be solved by the algorithms from [19,42]. In fact, we know from [4, THEOREM 4.2] that from a WNU on a domain of size kkkkk we can always derive a WNU (and also a cyclic operation) of any prime arity greater than kkkkk. Thus, we can find finitely many WNU operations on a domain of size kkkkk such that any constraint language preserved by a WNU is preserved by one of them. It remains to apply the algorithm for each WNU and return a solution if one of them gave a solution.
3. QUANTIFIED CSP
A natural generalization of the CSP is the Quantified Constraint Satisfaction Problem (QCSP), where we allow to use both existential and universal quantifiers. Formally, for a constraint language Γ,QCSP(Γ)Γ,QCSPâ¡(Γ)Gamma,QCSP(Gamma)\Gamma, \operatorname{QCSP}(\Gamma)Γ,QCSPâ¡(Γ) is the problem to evaluate a sentence of the form
where R1,…,Rs∈ΓR1,…,Rs∈ΓR_(1),dots,R_(s)in GammaR_{1}, \ldots, R_{s} \in \GammaR1,…,Rs∈Γ, and vi,j∈{x1,…,xn,y1,…,yn}vi,j∈x1,…,xn,y1,…,ynv_(i,j)in{x_(1),dots,x_(n),y_(1),dots,y_(n)}v_{i, j} \in\left\{x_{1}, \ldots, x_{n}, y_{1}, \ldots, y_{n}\right\}vi,j∈{x1,…,xn,y1,…,yn} for every i,ji,ji,ji, ji,j (see [16,23,24,37][16,23,24,37][16,23,24,37][16,23,24,37][16,23,24,37] ). Unlike the CSPCSPCSP\operatorname{CSP}CSP, the problem QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) can be PSpace-hard if the constraint language ΓΓGamma\GammaΓ is powerful enough. For example, QCSP({NAE})QCSPâ¡({NAE})QCSP({NAE})\operatorname{QCSP}(\{\mathrm{NAE}\})QCSPâ¡({NAE}) and QCSP({1IN3})QCSP({1IN3})QCSP({1IN3})\mathrm{QCSP}(\{1 \mathrm{IN} 3\})QCSP({1IN3}) on the domain A={0,1}A={0,1}A={0,1}A=\{0,1\}A={0,1} are PSpace-hard [25,27], and QCSP({≠})QCSPâ¡({≠})QCSP({!=})\operatorname{QCSP}(\{\neq\})QCSPâ¡({≠}) for |A|>2|A|>2|A| > 2|A|>2|A|>2 is also PSpace-hard [16]. Nevertheless, if ΓΓGamma\GammaΓ consists of linear equations modulo ppppp then QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) is tractable [16]. It was conjectured by Hubie Chen [22,24][22,24][22,24][\mathbf{2 2 , 2 4 ]}[22,24] that for any constraint language ΓΓGamma\GammaΓ the problem QCSP (Γ)(Γ)(Gamma)(\Gamma)(Γ) is either solvable in polynomial time, or NP-complete, or PSpace-complete. Recently, this conjecture was disproved in [48], where the authors found constraint languages ΓΓGamma\GammaΓ such that QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) is coNPcomplete (on a 3-element domain), DP-complete (on a 4-element domain), Θ2PΘ2PTheta_(2)^(P)\Theta_{2}^{P}Θ2P-complete (on a 10-element domain). Despite the whole zoo of the complexity classes, we still hope to obtain a full classification of the complexity for each constraint language ΓΓGamma\GammaΓ.
Below we consider the main idea that makes the problem easier than PSpace.
3.1. PGP reduction for Π2Î 2Pi_(2)\Pi_{2}Î 2 restrictions
For simplicity let us consider the Π2Î 2Pi_(2)\Pi_{2}Î 2-restriction of QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ), denoted QCSP2(Γ)QCSP2â¡(Γ)QCSP^(2)(Gamma)\operatorname{QCSP}^{2}(\Gamma)QCSP2â¡(Γ), in which the input is of the form
Such an instance holds whenever the conjunctive formula R1(…)∧⋯∧RS(…)R1(…)∧⋯∧RS(…)R_(1)(dots)^^cdots^^R_(S)(dots)R_{1}(\ldots) \wedge \cdots \wedge R_{S}(\ldots)R1(…)∧⋯∧RS(…) is solvable for any evaluation of x1,…,xnx1,…,xnx_(1),dots,x_(n)x_{1}, \ldots, x_{n}x1,…,xn, which gives us a reduction of the instance to |A|n|A|n|A|^(n)|A|^{n}|A|n instances of CSP(Γ∗)CSPâ¡Î“∗CSP(Gamma^(**))\operatorname{CSP}\left(\Gamma^{*}\right)CSPâ¡(Γ∗), where by Γ∗Γ∗Gamma^(**)\Gamma^{*}Γ∗ we denote Γ∪{(x=a)∣a∈A}Γ∪{(x=a)∣a∈A}Gamma uu{(x=a)∣a in A}\Gamma \cup\{(x=a) \mid a \in A\}Γ∪{(x=a)∣a∈A}. If we need to check |A|n|A|n|A|^(n)|A|^{n}|A|n tuples, which is exponentially many, this does not make the problem easier. Nevertheless, sometimes it is sufficient to check only polynomially many tuples. Let us consider a concrete example.
System of linear equations. Suppose A={0,1}A={0,1}A={0,1}A=\{0,1\}A={0,1} and ΓΓGamma\GammaΓ consists of linear equations in Z2Z2Z_(2)\mathbb{Z}_{2}Z2. Let us check that the instance (3.1) holds for (x1,…,xn)=(0,…,0)x1,…,xn=(0,…,0)(x_(1),dots,x_(n))=(0,dots,0)\left(x_{1}, \ldots, x_{n}\right)=(0, \ldots, 0)(x1,…,xn)=(0,…,0), and (x1,…,xn)=x1,…,xn=(x_(1),dots,x_(n))=\left(x_{1}, \ldots, x_{n}\right)=(x1,…,xn)=(0,…,0,1,0,…,0)(0,…,0,1,0,…,0)(0,dots,0,1,0,dots,0)(0, \ldots, 0,1,0, \ldots, 0)(0,…,0,1,0,…,0) for any position of 1 . To do this, we solve the CSP instance R1(…)∧R1(…)∧R_(1)(dots)^^R_{1}(\ldots) \wedgeR1(…)∧⋯∧Rs(…)∧⋀i=1n(xi=0)⋯∧Rs(…)∧⋀i=1n xi=0cdots^^R_(s)(dots)^^^^^_(i=1)^(n)(x_(i)=0)\cdots \wedge R_{s}(\ldots) \wedge \bigwedge_{i=1}^{n}\left(x_{i}=0\right)⋯∧Rs(…)∧⋀i=1n(xi=0), and for every j∈{1,2,…,n}j∈{1,2,…,n}j in{1,2,dots,n}j \in\{1,2, \ldots, n\}j∈{1,2,…,n} we solve the instance R1(…)∧⋯∧Rs(…)∧(xj=1)∧⋀i≠j(xi=0)R1(…)∧⋯∧Rs(…)∧xj=1∧⋀i≠j xi=0R_(1)(dots)^^cdots^^R_(s)(dots)^^(x_(j)=1)^^^^^_(i!=j)(x_(i)=0)R_{1}(\ldots) \wedge \cdots \wedge R_{s}(\ldots) \wedge\left(x_{j}=1\right) \wedge \bigwedge_{i \neq j}\left(x_{i}=0\right)R1(…)∧⋯∧Rs(…)∧(xj=1)∧⋀i≠j(xi=0). Each instance is a system of linear equations and can be solved in polynomial time. If at least one of the instances does not have a solution, then the instance (3.1) does not hold. Assume that all of them are satisfiable, then consider the relation ΔΔDelta\DeltaΔ defined by the following pp-formula over ΓΓGamma\GammaΓ :
Since ΓΓGamma\GammaΓ is preserved by x+y+z,Δx+y+z,Δx+y+z,Deltax+y+z, \Deltax+y+z,Δ is also preserved by x+y+zx+y+zx+y+zx+y+zx+y+z. Applying this operation to the tuples (0,0,…,0),(1,0,…,0),(0,1,0,…,0),…,(0,0,…,0,1)∈Δ(0,0,…,0),(1,0,…,0),(0,1,0,…,0),…,(0,0,…,0,1)∈Δ(0,0,dots,0),(1,0,dots,0),(0,1,0,dots,0),dots,(0,0,dots,0,1)in Delta(0,0, \ldots, 0),(1,0, \ldots, 0),(0,1,0, \ldots, 0), \ldots,(0,0, \ldots, 0,1) \in \Delta(0,0,…,0),(1,0,…,0),(0,1,0,…,0),…,(0,0,…,0,1)∈Δ coordinatewise, we derive that Δ={0,1}nΔ={0,1}nDelta={0,1}^(n)\Delta=\{0,1\}^{n}Δ={0,1}n, that is, ΔΔDelta\DeltaΔ contains all tuples and (3.1) holds. Thus, we showed that QCSP2(Γ)QCSP2â¡(Γ)QCSP^(2)(Gamma)\operatorname{QCSP}^{2}(\Gamma)QCSP2â¡(Γ) is solvable in polynomial time.
This idea can be generalized as follows. We say that a set of operations FFFFF (or an algebra (A;F))(A;F))(A;F))(A ; F))(A;F)) has the polynomially generated powers (PGP) property if there exists a polynomial p(n)p(n)p(n)p(n)p(n) such that AnAnA^(n)A^{n}An can be generated from p(n)p(n)p(n)p(n)p(n) tuples using operations of FFFFF. Another behavior that might arise is that there is an exponential function fffff so that the smallest generating sets for AnAnA^(n)A^{n}An require size at least f(n)f(n)f(n)f(n)f(n). We describe this as the exponentially generated powers (EGP) property. As it was proved in [43] these are the only two situations we could have on a finite domain. Moreover, it was shown that the generating set in the PGP case can be chosen to be very simple and efficiently computable. As a generating set of polynomial size, we can take the set of all tuples with at most kkkkk switches, where a switch is a position in (a1,…,an)a1,…,an(a_(1),dots,a_(n))\left(a_{1}, \ldots, a_{n}\right)(a1,…,an) such that ai≠ai+1ai≠ai+1a_(i)!=a_(i+1)a_{i} \neq a_{i+1}ai≠ai+1. This gives a polynomial reduction of QCSP2(Γ)QCSP2â¡(Γ)QCSP^(2)(Gamma)\operatorname{QCSP}^{2}(\Gamma)QCSP2â¡(Γ) to CSP(Γ∗)CSPâ¡Î“∗CSP(Gamma^(**))\operatorname{CSP}\left(\Gamma^{*}\right)CSPâ¡(Γ∗) if Pol(Γ)Polâ¡(Γ)Pol(Gamma)\operatorname{Pol}(\Gamma)Polâ¡(Γ) has the PGPPGPPGP\mathrm{PGP}PGP property.
3.2. A general PGP reduction
Let us show that the same idea can be applied to the general form of QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ). First, we show how to move universal quantifiers left and convert an instance into the Π2Î 2Pi_(2)\Pi_{2}Î 2-form. Notice that the sentence ∃y1∃y2…∃ys∀xΦ∃y1∃y2…∃ys∀xΦEEy_(1)EEy_(2)dots EEy_(s)AA x Phi\exists y_{1} \exists y_{2} \ldots \exists y_{s} \forall x \Phi∃y1∃y2…∃ys∀xΦ is equivalent to
where each ΦiΦiPhi_(i)\Phi_{i}Φi is obtained from ΦΦPhi\PhiΦ by renaming xxxxx by xixix^(i)x^{i}xi. In this way we can convert any instance ∃y1∀x1…∃yt∀xtΦ∃y1∀x1…∃yt∀xtΦEEy_(1)AAx_(1)dots EEy_(t)AAx_(t)Phi\exists y_{1} \forall x_{1} \ldots \exists y_{t} \forall x_{t} \Phi∃y1∀x1…∃yt∀xtΦ of QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) into the Π2Î 2Pi_(2)\Pi_{2}Î 2-restriction by moving all universal quantifiers left:
where each ΦiΦiPhi_(i)\Phi_{i}Φi is obtained from ΦΦPhi\PhiΦ by renaming the variables. The only problem with this reduction is that the number of variables and constraints could be exponential. Nevertheless, we can apply the PGP idea to this sentence. If Pol(Γ)Polâ¡(Γ)Pol(Gamma)\operatorname{Pol}(\Gamma)Polâ¡(Γ) has the PGP property then there exists a constant kkkkk such that it is sufficient to check (3.2) only on the tuples with at most kkkkk switches. Those kkkkk switches appear in at most kkkkk original xxxxx-variables and all the remaining variables can be fixed with constants. This allows reducing QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) to a sentence with a constant number of universal quantifiers or even remove all of them.
Theorem 3.1 ([45]). Suppose Pol(Γ)Polâ¡(Γ)Pol(Gamma)\operatorname{Pol}(\Gamma)Polâ¡(Γ) has the PGP property. Then QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) is polynomially equivalent to the modification of QCSP2(Γ)QCSP2â¡(Γ)QCSP^(2)(Gamma)\operatorname{QCSP}^{2}(\Gamma)QCSP2â¡(Γ) where sentences have at most |A||A||A||A||A| universally quantified variables.
Theorem 3.2 ([45]). Suppose Pol(Γ)Polâ¡(Γ)Pol(Gamma)\operatorname{Pol}(\Gamma)Polâ¡(Γ) has the PGPPGPPGPP G PPGP property. Then QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) is polynomially reduced to CSP(Γ∗)CSPâ¡Î“∗CSP(Gamma^(**))\operatorname{CSP}\left(\Gamma^{*}\right)CSPâ¡(Γ∗).
This idea gives us a complete classification of the complexity of QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) for a two-element domain.
Theorem 3.3 ([25, 27]). Suppose ΓΓGamma\GammaΓ is a constraint language on {0,1}{0,1}{0,1}\{0,1\}{0,1}. Then QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) is solvable in polynomial time if ΓΓGamma\GammaΓ is preserved by an idempotent WNU; QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) is PSpacecomplete otherwise.
It is known [39] that if ΓΓGamma\GammaΓ admits an idempotent WNU, then it is preserved by x+y+z,x∨y,x∧yx+y+z,x∨y,x∧yx+y+z,x vv y,x^^yx+y+z, x \vee y, x \wedge yx+y+z,x∨y,x∧y, or xy∨yz∨xzxy∨yz∨xzxy vv yz vv xzx y \vee y z \vee x zxy∨yz∨xz. Hence, to prove the above theorem, it is sufficient to check that these operations guarantee the PGP property, which by Theorem 3.2 gives a polynomial reduction to a tractable CSP. To show the PGP property, we verify that the tuples (0,0,…,0),(1,1,…,1),(1,0,…,0),(0,1,0,…,0),…,(0,…,0,1)(0,0,…,0),(1,1,…,1),(1,0,…,0),(0,1,0,…,0),…,(0,…,0,1)(0,0,dots,0),(1,1,dots,1),(1,0,dots,0),(0,1,0,dots,0),dots,(0,dots,0,1)(0,0, \ldots, 0),(1,1, \ldots, 1),(1,0, \ldots, 0),(0,1,0, \ldots, 0), \ldots,(0, \ldots, 0,1)(0,0,…,0),(1,1,…,1),(1,0,…,0),(0,1,0,…,0),…,(0,…,0,1) generate {0,1}n{0,1}n{0,1}^(n)\{0,1\}^{n}{0,1}n using any of the above operations.
3.3. Does EGP mean hard?
Thus, if Pol(Γ)Polâ¡(Γ)Pol(Gamma)\operatorname{Pol}(\Gamma)Polâ¡(Γ) has the PGP property then we have a nice reduction to CSP, and QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) belongs to NP. What can we say about the complexity of QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) if Pol(Γ)Polâ¡(Γ)Pol(Gamma)\operatorname{Pol}(\Gamma)Polâ¡(Γ) has the EGP property? Hubie Chen conjectured in [24] that QCSP(Γ)QCSP(Γ)QCSP(Gamma)\mathrm{QCSP}(\Gamma)QCSP(Γ) is PSpace-complete whenever Pol(Γ)Polâ¡(Γ)Pol(Gamma)\operatorname{Pol}(\Gamma)Polâ¡(Γ) has the EGP property.
For constraint languages ΓΓGamma\GammaΓ containing all constant relations, a characterization of Pol(Γ)Polâ¡(Γ)Pol(Gamma)\operatorname{Pol}(\Gamma)Polâ¡(Γ) that have the EGP property is given in [43], where it is shown that ΓΓGamma\GammaΓ must allow the pp-definition of relations τnÏ„ntau_(n)\tau_{n}Ï„n with the following special form.
Definition 3.4. Let α∪β=Aα∪β=Aalpha uu beta=A\alpha \cup \beta=Aα∪β=A, yet neither ααalpha\alphaα nor ββbeta\betaβ equals DDDDD. Let S=α3∪β3S=α3∪β3S=alpha^(3)uubeta^(3)S=\alpha^{3} \cup \beta^{3}S=α3∪β3 and τnÏ„ntau_(n)\tau_{n}Ï„n be the 3n3n3n3 n3n-ary relation given by ⋁i=1nS(xi,yi,zi)â‹i=1n Sxi,yi,zivvv_(i=1)^(n)S(x_(i),y_(i),z_(i))\bigvee_{i=1}^{n} S\left(x_{i}, y_{i}, z_{i}\right)â‹i=1nS(xi,yi,zi).
The complement to SSSSS represents the not-all-equal relation and the relations τnÏ„ntau_(n)\tau_{n}Ï„n allow for the encoding of the complement of Not-All-Equal 3-Satisfiability (where α∖βα∖βalpha\\beta\alpha \backslash \betaα∖β is 0 and β∖αβ∖αbeta\\alpha\beta \backslash \alphaβ∖α is 1). Thus, if one has polynomially computable (in nnnnn ) pp-definitions of τnÏ„ntau_(n)\tau_{n}Ï„n, then it is clear that QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) is co-NP-hard [22]. In light of this observation, it seemed that only a small step remained to proving the actual Chen Conjecture, at least with coNP-hard in place of PSpace-complete.
3.4. Surprising constraint language and the QCSP on a 3-element domain
As we saw in Section 2.7, the CSP is NP-hard if and only the we can pp-define (pp-construct) the not-all-equal relation. In the previous subsection, we mentioned that in the EGP case we can always pp-construct the complement to Not-All-Equal 3-Satisfability, which almost guarantees coNP-hardness. Surprisingly, two constraint languages ΓΓGamma\GammaΓ on A={0,1,2}A={0,1,2}A={0,1,2}A=\{0,1,2\}A={0,1,2} were discovered in [48] for which any pp-definition of τnÏ„ntau_(n)\tau_{n}Ï„n is of exponential size, which makes it impossible to use this reduction.
Theorem 3.5 ([48]). There exists a constraint language ΓΓGamma\GammaΓ on {0,1,2}{0,1,2}{0,1,2}\{0,1,2\}{0,1,2} such that
(1) Pol(Γ)Polâ¡(Γ)Pol(Gamma)\operatorname{Pol}(\Gamma)Polâ¡(Γ) has the EGP property,
(2) τnÏ„ntau_(n)\tau_{n}Ï„n is pp-definable over ΓΓGamma\GammaΓ
(3) any pp-definition of τnÏ„ntau_(n)\tau_{n}Ï„n for α={0,1}α={0,1}alpha={0,1}\alpha=\{0,1\}α={0,1} and β={0,2}β={0,2}beta={0,2}\beta=\{0,2\}β={0,2} has at least 2n2n2^(n)2^{n}2n variables, and
(4) QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) is solvable in polynomial time.
The algorithm in (4) consists of the following three steps. First, it reduces an instance to a Π2Î 2Pi_(2)\Pi_{2}Î 2-form ∀x1…∀xn∃y1…∃ymΦ∀x1…∀xn∃y1…∃ymΦAAx_(1)dots AAx_(n)EEy_(1)dots EEy_(m)Phi\forall x_{1} \ldots \forall x_{n} \exists y_{1} \ldots \exists y_{m} \Phi∀x1…∀xn∃y1…∃ymΦ. Then, by solving polynomially many CSPs, it calculates polynomially many evaluations to (x1,…,xn)x1,…,xn(x_(1),dots,x_(n))\left(x_{1}, \ldots, x_{n}\right)(x1,…,xn) we need to check. Finally, it checks that ΦΦPhi\PhiΦ has a solution for each of these evaluations. It is proved in [48] that this test guarantees that the instance holds.
This result was shocking because of several reasons. Not only it disproved the widely believed Chen Conjecture but showed that we need to worry about the existence of an efficient pp-definition. Before, if we could pp-define a strong relation (such as τnÏ„ntau_(n)\tau_{n}Ï„n ) then the problem was hard. Another surprising thing is that we have to calculate the evaluations of (x1,…,xn)x1,…,xn(x_(1),dots,x_(n))\left(x_{1}, \ldots, x_{n}\right)(x1,…,xn) we need to check, In fact, if we do not look inside ΦΦPhi\PhiΦ then we have to check all the tuples from {0,1}n{0,1}n{0,1}^(n)\{0,1\}^{n}{0,1}n.
Despite the fact that we are far from having a full classification of the complexity of the QCSP, we know the complexity for any constraint language on a 3-element domain containing all constant relations. This classification is given in terms of polymorphisms.
Theorem 3.6 ([48]). Suppose ΓΓGamma\GammaΓ is a finite constraint language on {0,1,2}{0,1,2}{0,1,2}\{0,1,2\}{0,1,2} containing all constant relations. Then QCSP(Γ)QCSP(Γ)QCSP(Gamma)\mathrm{QCSP}(\Gamma)QCSP(Γ) is either solvable in polynomial time, NPNPNPN PNP-complete, coNPcomplete, or PSpace-complete.
3.5. Conclusions
Unlike the CSP where the complexity is known for any constraint language ΓΓGamma\GammaΓ here the complexity is wide open.
Problem 2. What is the complexity of QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) ?
Moreover, we do not even have a conjecture describing the complexity. We know that for some constraint languages ΓΓGamma\GammaΓ the problem QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) is DP-complete and Θ2PΘ2PTheta_(2)^(P)\Theta_{2}^{P}Θ2P-complete, but we do not know whether there are some other complexity classes and whether we have finitely many of them.
Problem 3. What complexity classes (up to polynomial equivalence) can be expressed as QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) for some constraint language ΓΓGamma\GammaΓ ?
Now it is hard to believe that there will be a simple classification, that is why it is interesting to start with a 3-element domain (without constant relations) and 4-element domain. Probably, a more important problem is to describe all tractable cases assuming P≠NPP≠NPP!=NP\mathrm{P} \neq \mathrm{NP}P≠NP.
Problem 4. Describe all constraint languages ΓΓGamma\GammaΓ such that QCSP(Γ)QCSPâ¡(Γ)QCSP(Gamma)\operatorname{QCSP}(\Gamma)QCSPâ¡(Γ) is solvable in polynomial time.
4. OTHER VARIANTS OF CSP
The Quantified CSP is only one of many other variations and generalizations of the CSP whose complexity is still unknown. Here we list some of them.
4.1. CSP over an infinite domain
If we consider CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) for a constraint language on an infinite domain, the situation changes significantly. As was shown in [11], every computational problem is equivalent (under polynomial-time Turing reductions) to a problem of the form CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ). In [14] the authors gave a nice example of a constraint language ΓΓGamma\GammaΓ such that CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ) is undecidable. Let ΓΓGamma\GammaΓ consist of three relations (predicates) x+y=z,x⋅y=zx+y=z,xâ‹…y=zx+y=z,x*y=zx+y=z, x \cdot y=zx+y=z,xâ‹…y=z and x=1x=1x=1x=1x=1 over the set of all integers ZZZ\mathbb{Z}Z. Then the Hilbert's 10th problem can be expressed as CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ), which proves undecidability of CSP(Γ)CSPâ¡(Γ)CSP(Gamma)\operatorname{CSP}(\Gamma)CSPâ¡(Γ). Nevertheless, there are additional assumptions that send the CSP back to the class NP and make complexity classifications possible [8,12]. For more information about the infinite domain CSP and the algebraic approach, see [10,14].
4.2. Surjective Constraint Satisfaction Problem
A natural modification of the CSP is the Surjective Constraint Satisfaction Problem, where we want to find a surjective solution. Formally, for a constraint language ΓΓGamma\GammaΓ over a domain A,SCSP(Γ)A,SCSPâ¡(Γ)A,SCSP(Gamma)A, \operatorname{SCSP}(\Gamma)A,SCSPâ¡(Γ) is the following decision problem: given a formula
where all relations R1,…,RsR1,…,RsR_(1),dots,R_(s)R_{1}, \ldots, R_{s}R1,…,Rs are from ΓΓGamma\GammaΓ, decide whether there exists a surjective solution, that is, a solution with {x1,…,xn}=Ax1,…,xn=A{x_(1),dots,x_(n)}=A\left\{x_{1}, \ldots, x_{n}\right\}=A{x1,…,xn}=A. Probably, the most natural examples of the Surjective CSP are defined as the surjective graph homomorphism problem, which is equivalent to SCSP(Γ)SCSPâ¡(Γ)SCSP(Gamma)\operatorname{SCSP}(\Gamma)SCSPâ¡(Γ) where ΓΓGamma\GammaΓ consists of one binary relation that is viewed as a graph. An interesting fact about the complexity of the Surjective CSP is that its complexity remained unknown for many years even for very simple graphs and constraint languages. Three most popular examples of such long-standing problems are the complexity for the reflexive 4-cycle (undirected having a loop at each vertex) [38], the complexity for the nonreflexive 6-cycle (undirected without loops) [41], and the complexity of the No-Rainbow-Problem (SCSP({N})(SCSPâ¡({N})(SCSP({N})(\operatorname{SCSP}(\{N\})(SCSPâ¡({N}) where A={0,1,2}A={0,1,2}A={0,1,2}A=\{0,1,2\}A={0,1,2} and N={(a,b,c)∣{a,b,c}≠A})N={(a,b,c)∣{a,b,c}≠A})N={(a,b,c)∣{a,b,c}!=A})N=\{(a, b, c) \mid\{a, b, c\} \neq A\})N={(a,b,c)∣{a,b,c}≠A}) [46]. Even though these three problems turned out to be NP-complete, the complexity seems to be unknown even for graphs of size 5 and cycles.
Problem 5. What is the complexity of SCSP(Γ)SCSPâ¡(Γ)SCSP(Gamma)\operatorname{SCSP}(\Gamma)SCSPâ¡(Γ) ?
It was shown in [46] that the complexity of SCSP(Γ)SCSPâ¡(Γ)SCSP(Gamma)\operatorname{SCSP}(\Gamma)SCSPâ¡(Γ) cannot be described in terms of polymorphisms, which disproved the only conjecture about the complexity of SCSP(Γ)SCSPâ¡(Γ)SCSP(Gamma)\operatorname{SCSP}(\Gamma)SCSPâ¡(Γ) we know. This conjecture, formulated by Hubie Chen, says that SCSP(Γ)SCSPâ¡(Γ)SCSP(Gamma)\operatorname{SCSP}(\Gamma)SCSPâ¡(Γ) and CSP(Γ∗)CSPâ¡Î“∗CSP(Gamma^(**))\operatorname{CSP}\left(\Gamma^{*}\right)CSPâ¡(Γ∗) have the same complexity. Nevertheless, this conjecture still can hold for graphs.
Problem 6. Is it true that SCSP({R})SCSPâ¡({R})SCSP({R})\operatorname{SCSP}(\{R\})SCSPâ¡({R}) and CSP({R}∗)CSPâ¡{R}∗CSP({R}^(**))\operatorname{CSP}\left(\{R\}^{*}\right)CSPâ¡({R}∗) have the same complexity for any binary relation RRRRR ?
For more results on the complexity of the SCSP, see the survey [13].
4.3. Promise CSP
A natural generalization of the CSP is the Promise Constraint Satisfaction Problem, where a promise about the input is given (see [18,21]). Let Γ={(R1A,R1B),…,(RtA,RtB)}Γ=R1A,R1B,…,RtA,RtBGamma={(R_(1)^(A),R_(1)^(B)),dots,(R_(t)^(A),R_(t)^(B))}\Gamma=\left\{\left(R_{1}^{A}, R_{1}^{B}\right), \ldots,\left(R_{t}^{A}, R_{t}^{B}\right)\right\}Γ={(R1A,R1B),…,(RtA,RtB)}, where RiARiAR_(i)^(A)R_{i}^{A}RiA and RiBRiBR_(i)^(B)R_{i}^{B}RiB are relations of the same arity over the domains AAAAA and BBBBB, respectively. Then PCSP(Γ)PCSPâ¡(Γ)PCSP(Gamma)\operatorname{PCSP}(\Gamma)PCSPâ¡(Γ) is the following decision problem: given two conjunctive formulas
where (RijA,RijB)RijA,RijB(R_(i_(j))^(A),R_(i_(j))^(B))\left(R_{i_{j}}^{A}, R_{i_{j}}^{B}\right)(RijA,RijB) are from ΓΓGamma\GammaΓ for every jjjjj and vi,j∈{x1,…,xn}vi,j∈x1,…,xnv_(i,j)in{x_(1),dots,x_(n)}v_{i, j} \in\left\{x_{1}, \ldots, x_{n}\right\}vi,j∈{x1,…,xn} for every i,ji,ji,ji, ji,j, distinguish between the case when both of them are satisfiable, and when both of them are not satisfiable. Thus, we are given two CSP instances and a promise that if one has a solution then another has a solution. Usually, it is also assumed that there exists a mapping (homomorphism) h:A→Bh:A→Bh:A rarr Bh: A \rightarrow Bh:A→B such that h(RiA)⊆RiBhRiA⊆RiBh(R_(i)^(A))subeR_(i)^(B)h\left(R_{i}^{A}\right) \subseteq R_{i}^{B}h(RiA)⊆RiB for every iiiii. In this case, the satisfiability of the first formula implies
the satisfiability of the second one. To make sure that the promise can actually make an NP-hard problem tractable, see Example 2.8 in [21].
The most popular example of the Promise CSP is graph (k,l)(k,l)(k,l)(k, l)(k,l)-colorability, where we need to distinguish between kkkkk-colorable graphs and not even lllll-colorable, where k≤lk≤lk <= lk \leq lk≤l. This problem can be written as follows.
Problem 7. Let |A|=k,|B|=l,Γ={(≠A,≠B)}|A|=k,|B|=l,Γ=≠A,≠B|A|=k,|B|=l,Gamma={(!=_(A),!=_(B))}|A|=k,|B|=l, \Gamma=\left\{\left(\neq_{A}, \neq_{B}\right)\right\}|A|=k,|B|=l,Γ={(≠A,≠B)}. What is the complexity of PCSP(Γ)PCSPâ¡(Γ)PCSP(Gamma)\operatorname{PCSP}(\Gamma)PCSPâ¡(Γ) ?
Recently, it was proved [21] that (k,l)(k,l)(k,l)(k, l)(k,l)-colorability is NP-hard for l=2k−1l=2k−1l=2k-1l=2 k-1l=2k−1 and k≥3k≥3k >= 3k \geq 3k≥3 but even the complexity of (3,6)(3,6)(3,6)(3,6)(3,6)-colorability is still not known.
Even for a 2-element domain the problem is wide open, but recently a dichotomy for symmetric Boolean PCSP was proved [30].
Problem 8. Let A=B={0,1}A=B={0,1}A=B={0,1}A=B=\{0,1\}A=B={0,1}. What is the complexity of PCSP(Γ)PCSPâ¡(Γ)PCSP(Gamma)\operatorname{PCSP}(\Gamma)PCSPâ¡(Γ) ?
REFERENCES
[1] S. Arora and B. Barak, Computational complexity: a modern approach. Cambridge University Press, 2009.
[2] K. A. Baker and F. Pixley, Polynomial interpolation and the Chinese Remainder Theorem for algebraic systems. Math. Z. 143 (1975), 165-174.
[3] L. Barto, Z. Brady, A. Bulatov, M. Kozik, and D. Zhuk, Minimal Taylor algebras as a common framework for the three algebraic approaches to the CSP In 2021 36th annual ACM/IEEE symposium on logic in computer science (LICS), pp. 1-13, IEEE, 2021.
[4] L. Barto and M. Kozik, Absorbing subalgebras, cyclic terms, and the Constraint Satisfaction Problem. Log. Methods Comput. Sci. 8 (2012), no. 1.
[5] L. Barto and M. Kozik, Constraint satisfaction problems solvable by local consistency methods. J. ACM 61 (2014), no. 1, 1-19.
[6] L. Barto, A. Krokhin, and R. Willard, Polymorphisms, and how to use them.
Dagstuhl Follow-Ups 7, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
[7] L. Barto, J. Opršal, and M. Pinsker, The wonderland of reflections. Israel J. Math. 223 (2018), no. 1, 363-398.
[8] L. Barto and M. Pinsker, The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In 2016 31st annual ACM/IEEE symposium on logic in computer science (LICS), pp. 1-8, IEEE, 2016.
[9] J. Berman, P. Idziak, P. Marković, R. McKenzie, M. Valeriote, and R. Willard, Varieties with few subalgebras of powers. Trans. Amer. Math. Soc. 362 (2010), no. 3, 1445-1473.
[10] M. Bodirsky, Complexity classification in infinite-domain constraint satisfaction. 2012, arXiv:1201.0856.
[11] M. Bodirsky and M. Grohe, Non-dichotomies in constraint satisfaction complexity. In International colloquium on automata, languages, and programming, pp. 184-196, Springer, 2008.
[12] M. Bodirsky and J. Kára, The complexity of temporal constraint satisfaction problems. J. ACM 57 (2010), no. 2, 9.
[13] M. Bodirsky, J. Kára, and B. Martin, The complexity of surjective homomorphism problems - a survey. Discrete Appl. Math. 160 (2012), no. 12, 1680-1690.
[14] M. Bodirsky and M. Mamino, Constraint satisfaction problems over numeric domains. Dagstuhl Follow-Ups 7, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
[15] V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov, Galois theory for post algebras parts I and II. Cybernetics 5 (1969), 243-252, 531-539. 9
[16] F. Börner, A. A. Bulatov, H. Chen, P. Jeavons, and A. A. Krokhin, The complexity of constraint satisfaction games and QCSP. Inform. and Comput. 207 (2009), no. 9, 923-944.
[17] J. Brakensiek, S. Gopi, and V. Guruswami, CSPs with global modular constraints: algorithms and hardness via polynomial representations. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pp. 590-601, Association for Computing Machinery, 2019.
[18] J. Brakensiek and V. Guruswami, Promise constraint satisfaction: structure theory and a symmetric boolean dichotomy. In Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, pp. 1782-1801, SIAM, 2018.
[19] A. A. Bulatov, A dichotomy theorem for nonuniform CSPs. In 2017 IEEE 58th annual symposium on foundations of computer science (FOCS), pp. 319-330, IEEE, 2017.
[20] A. A. Bulatov, A dichotomy theorem for nonuniform CSPs. 2017, arXiv:1703.03021.
[21] J. BulÃn, A. Krokhin, and J. OprÅ¡al, Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pp. 602-613, ACM, 2019.
[22] C. Carvalho, B. Martin, and D. Zhuk, The complexity of quantified constraints using the algebraic formulation. In 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21-25, 2017 Aalborg, Denmark, pp. 27:1-27:14, Leibniz Center for Informatics, 2017.
[23] H. Chen, The complexity of quantified constraint satisfaction: Collapsibility, sink algebras, and the three-element case. SIAM J. Comput. 37 (2008), no. 5, 1674−17011674−17011674-17011674-17011674−1701.
[24] H. Chen, Meditations on quantified constraint satisfaction. In Logic and program semantics - essays dedicated to Dexter Kozen on the occasion of his 60th birthday, pp. 35-49, Springer, 2012.
[25] N. Creignou, S. Khanna, and M. Sudan, Complexity classifications of boolean constraint satisfaction problems. SIAM, 2001.
[26] N. Creignou, H. Schnoor, and I. Schnoor, Non-uniform boolean constraint satisfaction problems with cardinality constraint. In International workshop on computer science logic, pp. 109-123, Springer, 2008.
[28] T. Feder and M. Y. Vardi, Monotone monadic SNP and constraint satisfaction. In Proceedings of the twenty-fifth annual ACM symposium on theory of computing, pp. 612-622, Association for Computing Machinery, 1993.
[29] T. Feder and M. Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28 (1999), no. 1, 57-104.
[30] M. Ficak, M. Kozik, M. Olsak, and S. Stankiewicz, Dichotomy for symmetric boolean PCSPs. 2019, arXiv:1904.12424.
[31] D. Geiger, Closed systems of functions and predicates. Pacific J. Math. 27 (1968), no. 1,95−1001,95−1001,95-1001,95-1001,95−100.
[32] W. H. Greub, Linear algebra. Grad. Texts in Math. 23, Springer, 2012.
[33] P. Idziak, P. Marković, R. McKenzie, M. Valeriote, and R. Willard, Tractability and learnability arising from algebras with few subpowers. SIAM J. Comput. 39 (2010), no. 7, 3023-3037.
[34] P. Jeavons, On the algebraic structure of combinatorial problems. Theoret. Comput. Sci. 200 (1998), no. 1-2, 185-204.
[35] P. Jeavons, D. Cohen, and M. C. Cooper, Constraints, consistency and closure. Artif. Intell. 101 (1998), no. 1-2, 251-265.
[36] M. Kozik, Weak consistency notions for all the CSPs of bounded width. In 2016 31st annual ACM/IEEE symposium on logic in computer science (LICS), pp. 1-9, IEEE, 2016.
[37] B. Martin, Quantified Constraints in Twenty Seventeen. In The constraint satisfaction problem: complexity and approximability, edited by A. Krokhin and S. Zivny, pp. 327-346, Dagstuhl Follow-Ups 7, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017.
[38] B. Martin and D. Paulusma, The computational complexity of disconnected cut and 2 k2-partition. J. Combin. Theory Ser. B 111 (2015), 17-37.
[39] E. L. Post, The two-valued iterative systems of mathematical logic. Ann. of Math. Stud. 5, Princeton University Press, Princeton, NJ, 1941.
[40] T. J. Schaefer, The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on theory of computing, STOC'78, pp. 216-226, ACM, New York, NY, USA, 1978.
[41] N. Vikas, Computational complexity of graph partition under vertex-compaction to an irreflexive hexagon. In 42nd international symposium on mathematical foundations of computer science, MFCS 2017, pp. 69:1-69:14, LIPIcs 83, Leibniz Center for Informatics, 2017.
[42] D. Zhuk, A proof of CSP dichotomy conjecture. In 2017 IEEE 58th annual symposium on foundations of computer science (FOCS), pp. 331-342, IEEE, 2017.
[43] D. Zhuk, The size of generating sets of powers. J. Combin. Theory Ser. A 167 (2019), 91-103.
[44] D. Zhuk, A proof of the CSP dichotomy conjecture. J. ACM 67 (2020), no. 5, 1−781−781-781-781−78.
[45] D. Zhuk, The complexity of the Quantified CSP having the polynomially generated powers property. 2021, arXiv:2110.09504.
[46] D. Zhuk, No-rainbow problem and the surjective constraint satisfaction problem. In 2021 36th annual ACM/IEEE symposium on logic in computer science (LICS), pp. 1-7, IEEE, 2021.
[47] D. Zhuk, Strong subalgebras and the constraint satisfaction problem. J. Mult.Valued Logic Soft Comput. 36 (2021).
[48] D. Zhuk and B. Martin, QCSP monsters and the demise of the Chen conjecture. In Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, pp. 91-104, 2020.
DMITRIY ZHUK
Department of Mechanics and Mathematics, Lomonosov Moscow State University, Vorobjovy Gory, 119899 Moscow, Russia, zhuk @intsys.msu.ru
ALGEBRA
A TOTALLY DISCONNECTED INVITATION TO LOCALLY COMPACT GROUPS
PIERRE-EMMANUEL CAPRACE ANDGEORGE A. WILLIS
ABSTRACT
We present a selection of results contributing to a structure theory of totally disconnected locally compact groups.
Locally compact group, profinite group, amenable group, simple group, topological dynamics, commensurated subgroup, minimising subgroup, flat group of automorphisms
1. INTRODUCTION
Locally compact groups have attracted sustained attention because, on the one hand, rich classes of these groups have fruitful connections with other fields and, on the other, they have a well-developed theory that underpins those connections and delineates group structure. Salient features of this theory are the existence of a left-invariant, or Haar, measure; and the decomposition of a general group into pieces, many of which may be described concretely and in detail.
Haar measure permits representations of a general locally compact group by operators on spaces of measurable functions, and is thus the foundation for abstract harmonic analysis. Connections with partial differential equations, physics, and number theory come about through these representations. Locally compact groups are the largest class for which an invariant measure exists and for which harmonic analysis can be done in this form, as was shown by A. Weil [81].
The decomposition theory of an arbitrary locally compact group GGGGG begins with the short exact sequence
0→G∘→G→G/G∘→00→G∘→G→G/G∘→00rarrG^(@)rarr G rarr G//G^(@)rarr00 \rightarrow G^{\circ} \rightarrow G \rightarrow G / G^{\circ} \rightarrow 00→G∘→G→G/G∘→0
in which the closed normal subgroup G∘G∘G^(@)G^{\circ}G∘ is the connected component of the identity. The Gleason-Yamabe theorem [73, тн. 6.0.11] applies to G∘G∘G^(@)G^{\circ}G∘ to show that it is a projective limit of connected Lie groups, and powerful tools from the theory of Lie groups may thus be brought to bear on G∘G∘G^(@)G^{\circ}G∘. Groups occurring in physics and differential equations are often Lie groups. The quotient G/G∘G/G∘G//G^(@)G / G^{\circ}G/G∘ is a totally disconnected locally compact group (abbreviated tdlc group). Lie groups over local fields are important examples of tdlc groups having links to number theory and algebraic geometry (see, for example, [49,69][49,69][49,69][49,69][49,69] ). Unlike the connected case however, many other significant tdlc groups, such as the automorphism groups of locally finite trees first studied in [76], cannot be approximated by Lie groups. While substantial progress has been made with our understanding of tdlc groups much remains to be done before it could be said that the structure theory has reached maturity. This article surveys our current state of knowledge, much of which is founded on a theorem of van Dantzig, [77], which ensures that a tdlc group GGGGG has a basis of identity neighborhoods consisting of compact open subgroups.
Decompositions of general tdlc groups are described in Section 2. This section includes a discussion of the so-called elementary groups, which are those built from discrete and compact groups by standard operations. Discrete and compact groups are large domains of study in their own right and it is seen how elementary groups can be factored out in the analysis of a general tdlc group. Simple groups are an important aspect of any decomposition theory and what is known about them is summarized in Section 3. This includes a local structure theory and the extent to which local structure determines the global structure of the group. Section 4 treats scale methods, which associate invariants and special subgroups to abelian groups of automorphisms and which in some circumstances substitute for the Lie methods available for connected groups. A unifying theme of our approach is the dynamics of the conjugation action: Section 2 is concerned with the conjugation action of GGGGG on its closed subnormal subgroups, Section 3 uses in an essential way the conjugation
action of GGGGG on its closed subgroups, especially those that are locally normal, while Section 4 concerns the dynamics of the conjugation action of cyclic subgroups (and, more generally, flat subgroups) on the topological space GGGGG. Section 5 highlights a few open questions and directions for further research.
2. DECOMPOSITION THEORY
2.1. Normal subgroup structure
Finite groups, Lie groups, and algebraic groups constitute three of the most important classes of groups. Their respective structure theories are deep and far-reaching. One of the common themes consists in reducing problems concerning a given group GGGGG in one of these classes to problems about simple groups in the corresponding class, and then tackling the reduced problem by invoking classification results. Striking illustrations of this approach in the case of finite groups can be consulted in R. Guralnick's ICM address [43].
Since the category of locally compact groups contains all discrete groups, hence all groups, developing a similar theory for locally compact groups is hopeless. Nevertheless, the possibility to construct meaningful "decompositions of locally compact groups into simple pieces" has been highlighted in [23]. Wide-ranging results have subsequently been established by C. Reid and P. Wesolek in a series of papers [63,64], some of whose contributions are summarized below. A more in-depth survey can be consulted in [62].
Given closed normal subgroups K,LK,LK,LK, LK,L of a locally compact group GGGGG, the quotient group K/LK/LK//LK / LK/L is called a chief factor of GGGGG if LLLLL is strictly contained in KKKKK and for every closed normal subgroup NNNNN of GGGGG with L≤N≤KL≤N≤KL <= N <= KL \leq N \leq KL≤N≤K, we have N=LN=LN=LN=LN=L or N=KN=KN=KN=KN=K. Given a closed normal subgroup NNNNN of GGGGG, the quotient Q=G/NQ=G/NQ=G//NQ=G / NQ=G/N is a chief factor if and only if QQQQQ is topologically simple, i.e., QQQQQ is nontrivial and the only closed normal subgroups of QQQQQ are {1}{1}{1}\{1\}{1} and QQQQQ. More generally, every chief factor Q=K/LQ=K/LQ=K//LQ=K / LQ=K/L is topologically characteristically simple, i.e., the only closed subgroups of QQQQQ that are invariant under all homeomorphic automorphisms of QQQQQ are {1}{1}{1}\{1\}{1} and QQQQQ. A topological group is called compactly generated if it has a compact generating set.
Theorem 2.1 (See [64, тн. 1.3]). Every compactly generated tdlc group GGGGG has a finite series {1}=G0<G1<G2<⋯<Gn=G{1}=G0<G1<G2<⋯<Gn=G{1}=G_(0) < G_(1) < G_(2) < cdots < G_(n)=G\{1\}=G_{0}<G_{1}<G_{2}<\cdots<G_{n}=G{1}=G0<G1<G2<⋯<Gn=G of closed normal subgroups such that for all i=1,…,ni=1,…,ni=1,dots,ni=1, \ldots, ni=1,…,n, the quotient Gi/Gi−1Gi/Gi−1G_(i)//G_(i-1)G_{i} / G_{i-1}Gi/Gi−1 is compact, or discrete infinite, or a chief factor of GGGGG which is noncompact, nondiscrete, and second countable.
A normal series as in Theorem 2.1 is called an essentially chief series. The theorem obviously has no content if GGGGG is compact or discrete. Let us illustrate Theorem 2.1 with two examples.
Example 2.2. Let IIIII be a set and for each i∈Ii∈Ii in Ii \in Ii∈I, let GiGiG_(i)G_{i}Gi be a tdlc group and Ui≤GiUi≤GiU_(i) <= G_(i)U_{i} \leq G_{i}Ui≤Gi be a compact open subgroup. The restricted product of (Gi,Ui)i∈IGi,Uii∈I(G_(i),U_(i))_(i in I)\left(G_{i}, U_{i}\right)_{i \in I}(Gi,Ui)i∈I, denoted by ⨁i∈I(Gi,Ui)â¨i∈I Gi,Uibigoplus_(i in I)(G_(i),U_(i))\bigoplus_{i \in I}\left(G_{i}, U_{i}\right)â¨i∈I(Gi,Ui), is the subgroup of ∏i∈IGiâˆi∈I Giprod_(i in I)G_(i)\prod_{i \in I} G_{i}âˆi∈IGi consisting of those tuples (gi)i∈Igii∈I(g_(i))_(i in I)\left(g_{i}\right)_{i \in I}(gi)i∈I such that gi∈Uigi∈Uig_(i)inU_(i)g_{i} \in U_{i}gi∈Ui for all but finitely many i∈Ii∈Ii in Ii \in Ii∈I. It is endowed with the unique tdlc group topology such that
the inclusion ∏i∈IUi→⨁i∈I(Gi,Ui)âˆi∈I Ui→â¨i∈I Gi,Uiprod_(i in I)U_(i)rarrbigoplus_(i in I)(G_(i),U_(i))\prod_{i \in I} U_{i} \rightarrow \bigoplus_{i \in I}\left(G_{i}, U_{i}\right)âˆi∈IUi→â¨i∈I(Gi,Ui) is continuous and open. Given a prime ppppp, set M(p)=⨁n∈Z(PSL2(Qp),PSL2(Zp))M(p)=â¨n∈Z PSL2Qp,PSL2ZpM(p)=bigoplus_(n inZ)(PSL_(2)(Q_(p)),PSL_(2)(Z_(p)))M(p)=\bigoplus_{n \in \mathbf{Z}}\left(\mathrm{PSL}_{2}\left(\mathbf{Q}_{p}\right), \mathrm{PSL}_{2}\left(\mathbf{Z}_{p}\right)\right)M(p)=â¨n∈Z(PSL2(Qp),PSL2(Zp)). The cyclic group ZZZ\mathbf{Z}Z naturally acts on M(p)M(p)M(p)M(p)M(p) by shifting the coordinates. The semidirect product G(p)=M(p)⋊ZG(p)=M(p)⋊ZG(p)=M(p)><|ZG(p)=M(p) \rtimes \mathbf{Z}G(p)=M(p)⋊Z is a compactly generated tdlc group, with an essentially chief series given by {1}<M(p)<G(p){1}<M(p)<G(p){1} < M(p) < G(p)\{1\}<M(p)<G(p){1}<M(p)<G(p). The group M(p)M(p)M(p)M(p)M(p) is not compactly generated. It has minimal closed normal subgroups, but does not admit any finite essentially chief series, which illustrates the necessity of the compact generation hypothesis in Theorem 2.1.
Example 2.3. A more elaborate construction in [63, §9] yields an example of a compactly generated tdlc group G′(p)G′(p)G^(')(p)G^{\prime}(p)G′(p) with an essentially chief series given by {1}<H(p)<G′(p){1}<H(p)<G′(p){1} < H(p) < G^(')(p)\{1\}<H(p)<G^{\prime}(p){1}<H(p)<G′(p) such that G′(p)/H(p)≅ZG′(p)/H(p)≅ZG^(')(p)//H(p)~=ZG^{\prime}(p) / H(p) \cong \mathbb{Z}G′(p)/H(p)≅Z and H(p)H(p)H(p)H(p)H(p) has a nested chain of closed normal subgroups (H(p)n)H(p)n(H(p)_(n))\left(H(p)_{n}\right)(H(p)n) indexed by ZZZ\mathbf{Z}Z, permuted transitively by the conjugation G′(p)G′(p)G^(')(p)G^{\prime}(p)G′(p)-action, and such that H(p)n/H(p)n−1≅M(p)H(p)n/H(p)n−1≅M(p)H(p)_(n)//H(p)_(n-1)~=M(p)H(p)_{n} / H(p)_{n-1} \cong M(p)H(p)n/H(p)n−1≅M(p) for all n∈Zn∈Zn inZn \in \mathbf{Z}n∈Z.
A tdlc group is compactly generated if and only if it is capable of acting continuously, properly, with finitely many vertex orbits, by automorphisms on a connected locally finite graph. For a given compactly generated tdlc group GGGGG, vertex-transitive actions on graphs are afforded by the following construction. Given a compact open subgroup U<GU<GU < GU<GU<G, guaranteed to exist by van Dantzig's theorem, and a symmetric compact generating set ΣΣSigma\SigmaΣ of GGGGG, we construct a graph ΓΓGamma\GammaΓ whose vertex set is the coset space G/UG/UG//UG / UG/U by declaring that the vertices gUgUgUg UgU and hUhUhUh UhU are adjacent if h−1gh−1gh^(-1)gh^{-1} gh−1g belongs to UΣUUΣUU Sigma UU \Sigma UUΣU. The fact that ΣΣSigma\SigmaΣ generates GGGGG ensures that ΓΓGamma\GammaΓ is connected. Moreover, GGGGG acts vertex-transitively by automorphisms on ΓΓGamma\GammaΓ. Since UUUUU is compact open, the set UΣUUΣUU Sigma UU \Sigma UUΣU is a finite union of double cosets modulo UUUUU; this implies that ΓΓGamma\GammaΓ is locally finite, i.e., the degree of each vertex is finite. Notice that all vertices have the same degree since ΓΓGamma\GammaΓ is homogeneous. The graph ΓΓGamma\GammaΓ is called a Cayley-Abels graph for GGGGG, since its construction was first envisaged by H. Abels [1, BEISPIEL 5.2] and specializes to a Cayley graph when GGGGG is discrete and U={1}U={1}U={1}U=\{1\}U={1}. The proof of Theorem 2.1 proceeds by induction on the minimum degree of a Cayley-Abels graph.
2.2. Elementary groups
By its very nature, Theorem 2.1 highlights the special role played by compact and discrete groups. A conceptual approach to studying the role of compact and discrete groups in the structure theory of tdlc groups is provided by P. Wesolek's notion of elementary groups. That concept is inspired by the class of elementary amenable discrete groups introduced by M. Day [33]. It is defined as the smallest class EEE\mathscr{E}E of second countable tdlc groups (abbreviated tdlcsc) containing all countable discrete groups and all compact tdlcsc groups, which is stable under the following two group theoretic operations:
Given a tdlcsc group GGGGG and a closed normal subgroup NNNNN, if N∈EN∈EN inEN \in \mathscr{E}N∈E and G/N∈EG/N∈EG//N inEG / N \in \mathscr{E}G/N∈E, then G∈EG∈EG inEG \in \mathscr{E}G∈E. In other words EEE\mathscr{E}E is stable under group extensions.
Given a tdlcsc group GGGGG and a directed set (Oi)i∈IOii∈I(O_(i))_(i in I)\left(O_{i}\right)_{i \in I}(Oi)i∈I of open subgroups, if Oi∈EOi∈EO_(i)inEO_{i} \in \mathscr{E}Oi∈E for all iiiii and if G=⋃iOiG=⋃i OiG=uuu_(i)O_(i)G=\bigcup_{i} O_{i}G=⋃iOi, then G∈EG∈EG inEG \in \mathscr{E}G∈E. In other words EEE\mathscr{E}E is stable under directed unions of open subgroups.
(The class EEE\mathscr{E}E has a natural extension beyond the second countable case, see [29, $6]. For simplicity of the exposition, we stick to the second countable case here.) Using the permanence properties of the class EEE\mathscr{E}E, it can be shown that every tdlcsc group GGGGG has a largest closed normal subgroup that is elementary; it is denoted by RE(G)RE(G)R_(E)(G)R_{\mathscr{E}}(G)RE(G) and called the elementary radical of GGGGG. It indeed behaves as a radical, in the sense that it contains all elementary closed normal subgroups, and satisfies RE(G/RE(G))={1}REG/RE(G)={1}R_(E)(G//R_(E)(G))={1}R_{\mathscr{E}}\left(G / R_{\mathscr{E}}(G)\right)=\{1\}RE(G/RE(G))={1}, see [82, 87.2]. Further properties of the quotient G/RE(G)G/RE(G)G//R_(E)(G)G / R_{\mathscr{E}}(G)G/RE(G) will be mentioned in Section 3 below.
Similarly as for elementary amenable discrete groups, the class EEE\mathscr{E}E admits a canonical rank function ξ:E→ω1ξ:E→ω1xi:Erarromega_(1)\xi: \mathscr{E} \rightarrow \omega_{1}ξ:E→ω1, taking values in the set ω1ω1omega_(1)\omega_{1}ω1 of countable ordinals, called the decomposition rank. It measures the complexity of a given group G∈EG∈EG inEG \in \mathscr{E}G∈E. By convention, the function ξξxi\xiξ is extended to all tdlcsc groups by setting ξ(G)=ω1ξ(G)=ω1xi(G)=omega_(1)\xi(G)=\omega_{1}ξ(G)=ω1 for each nonelementary tdlcsc group GGGGG. We refer to [82], [83] and [62, $5]. Let us merely mention here that the class EEE\mathscr{E}E has remarkable permanence properties (e.g., it is stable under passing to closed subgroups and quotient groups), that the rank function has natural monotonicity properties, and that a nontrivial compactly generated group G∈EG∈EG inEG \in \mathscr{E}G∈E has a nontrivial discrete quotient. It follows in particular that if GGGGG is a tdlcsc group having a closed subgroup H≤GH≤GH <= GH \leq GH≤G admitting a nondiscrete compactly generated topologically simple quotient, then G∉EG∉EG!inEG \notin \mathscr{E}G∉E. Therefore, the only compactly generated topologically simple groups in EEE\mathscr{E}E are discrete. On the other hand, the class EEE\mathscr{E}E contains numerous topologically simple groups that are not compactly generated, e.g. simple groups that are regionally elliptic, i.e., groups that can be written as a directed union of compact open subgroups. Those groups have decomposition rank 2. Explicit examples appear in [88,§3][88,§3][88,§3][88, \S 3]§[88,§3] or [19,§6][19,§6][19,§6][19, \S 6]§[19,§6].
Theorem 2.4 (See [62, cor. 5]). Let GGGGG be a compactly generated tdlc group and let {1}=A0<A1<A2<⋯<Am=G{1}=A0<A1<A2<⋯<Am=G{1}=A_(0) < A_(1) < A_(2) < cdots < A_(m)=G\{1\}=A_{0}<A_{1}<A_{2}<\cdots<A_{m}=G{1}=A0<A1<A2<⋯<Am=G and {1}=B0<B1<B2<⋯<Bn=G{1}=B0<B1<B2<⋯<Bn=G{1}=B_(0) < B_(1) < B_(2) < cdots < B_(n)=G\{1\}=B_{0}<B_{1}<B_{2}<\cdots<B_{n}=G{1}=B0<B1<B2<⋯<Bn=G be essentially chief series for GGGGG. Then for each i∈{0,1,…,m}i∈{0,1,…,m}i in{0,1,dots,m}i \in\{0,1, \ldots, m\}i∈{0,1,…,m}, if Ai/Ai−1Ai/Ai−1A_(i)//A_(i-1)A_{i} / A_{i-1}Ai/Ai−1 is a chief factor with a trivial quasicenter, there is a unique jjjjj such that Bj/Bj−1Bj/Bj−1B_(j)//B_(j-1)B_{j} / B_{j-1}Bj/Bj−1 is a chief factor with a trivial quasicenter that is associated with Ai/Ai−1Ai/Ai−1A_(i)//A_(i-1)A_{i} / A_{i-1}Ai/Ai−1. In other words, the association relation establishes a bijection between the sets of chief factors with a trivial quasicenter appearing respectively in the two series.
The natural next question is to ask what can be said about chief factors. By the discussion above, one should focus on properties that are invariant under the association relation. Following Reid-Wesolek, an association class of nonabelian chief factors is called a chief block, and a group property shared by all members of a chief block is called a block property. The following are shown in [63] to be block properties: compact generation, amenability, having a trivial quasicenter, having a dense quasicenter, being elementary of a given decomposition rank.
As mentioned above, every chief factor is topologically characteristically simple. In particular, a compactly generated chief factor is subjected to the following description.
Theorem 2.5 (See [23, COR. D] and [22, REM. 3.10]). Let G be a compactly generated nondiscrete, noncompact tdlc group which is topologically characteristic simple. Then there is a compactly generated nondiscrete topologically simple tdlc group SSSSS, an integer d≥1d≥1d >= 1d \geq 1d≥1 and an injective continuous homomorphism Sd=S×⋯×S→GSd=S×⋯×S→GS^(d)=S xx cdots xx S rarr GS^{d}=S \times \cdots \times S \rightarrow GSd=S×⋯×S→G of the direct product of ddddd copies of SSSSS, such that the image of each simple factor is a closed normal subgroup of GGGGG, and the image of the whole product is dense.
In the setting of Theorem 2.5, we say that GGGGG is the quasiproduct ddddd copies of the simple group SSSSS. Theorem 2.5 provides a major incentive to study the compactly generated nondiscrete topologically simple tdlc groups. We shall come back to this theme in Section 3 below.
Developing a meaningful structure theory for topologically characteristically simple tdlc groups that are not compactly generated is very challenging. Remarkably, significant results have been established by Reid-Wesolek [63] under the mild assumption of second countability (abbreviated sc). In spite of the noncompact generation, they introduce an appropriate notion of chief blocks, and show that there are only three possible configurations for the arrangement of chief blocks in a topologically characteristically simple tdlcsc group GGGGG, that they call weak type, semisimple type, and stacking type. Moreover, if GGGGG is of weak type, then it is automatically elementary of decomposition rank ≤ω+1≤ω+1<= omega+1\leq \omega+1≤ω+1. The topologically characteristically simple groups M(p)M(p)M(p)M(p)M(p) and H(p)H(p)H(p)H(p)H(p) appearing in Examples 2.2 and 2.3 above are respectively of semisimple type and stacking type. We refer to [63] and [62] for details.
3. SIMPLE GROUPS
Let SSS\mathscr{S}S be the class of nondiscrete, compactly generated, topologically simple locally compact groups and Std Std S_("td ")\mathscr{S}_{\text {td }}Std be the subclass consisting of the totally disconnected members of SSS\mathscr{S}S. By the Gleason-Yamabe theorem [73, тн. 6.0.11], all elements of S∖Std S∖Std S\\S_("td ")\mathscr{S} \backslash \mathscr{S}_{\text {td }}S∖Std are connected simple Lie groups. Prominent examples of groups in StdStdS_(td)\mathscr{S}_{\mathrm{td}}Std are provided by simple algebraic groups over non-Archimedean local fields, irreducible complete Kac-Moody groups over finite fields, certain groups acting on trees and many more, see [28, APPENDIX A]. A systematic study of the class Std Std S_("td ")\mathscr{S}_{\text {td }}Std as a whole has been initiated by Caprace-Reid-Willis in [28], and continued with P. Wesolek in [29] and with A. Le Boudec in [22]. We now outline some of their contributions. Another survey of the properties of nondiscrete simple locally compact groups can be consulted in [17]; the present account emphasizes more recent results.
3.1. Dense embeddings and local structure
As mentioned in Section 2.3 above, the failure of the second isomorphism theorem for topological groups naturally leads one to consider dense embeddings, i.e., continuous injective homomorphisms with dense image. If G,HG,HG,HG, HG,H are locally compact groups and ψψpsi\psiψ : H→GH→GH rarr GH \rightarrow GH→G is a dense embedding, and if GGGGG is a connected simple Lie group or a simple algebraic group over a local field, then HHHHH is discrete or ψψpsi\psiψ is an isomorphism (see [29, §3]). This property however generally fails for groups G∈SG∈SG inSG \in \mathscr{S}G∈S; see [50] for explicit examples. Nevertheless, as soon as the group HHHHH is nondiscrete, it turns out that key structural features of GGGGG are inherited by the dense subgroup HHHHH. To state this more precisely, we recall the definition of the class RRR\mathscr{R}R of robustly monolithic groups, introduced in [29]. A tdlc group GGGGG is robustly monolithic if the intersection MMMMM of all nontrivial closed normal subgroups of GGGGG is nontrivial, if MMMMM is topologically simple and if MMMMM has a compactly generated open subgroup without any nontrivial compact normal subgroup. The class RRR\mathscr{R}R contains StdStdS_(td)\mathscr{S}_{\mathrm{td}}Std and that inclusion is strict. The following result provides the main motivation to enlarge one's viewpoint by considering RRR\mathscr{R}R instead of the smaller class StdStdS_(td)\mathscr{S}_{\mathrm{td}}Std.
Theorem 3.1 (See [29, тн. 1.1.2]). Let G,HG,HG,HG, HG,H be tdlc groups and ψ:H→Gψ:H→Gpsi:H rarr G\psi: H \rightarrow Gψ:H→G be a dense embedding. If G∈RG∈RG inRG \in \mathscr{R}G∈R and HHHHH is nondiscrete, then H∈RH∈RH inRH \in \mathscr{R}H∈R.
We emphasize that in general HHHHH is not topologically simple even in the special case where G∈StdG∈StdG inS_(td)G \in \mathscr{S}_{\mathrm{td}}G∈Std.
Recall that a compact GGGGG-space XXXXX is called minimal if every GGGGG-orbit is dense. It is called strongly proximal if the closure of each GGGGG-orbit in the space of probability measures on XXXXX contains a Dirac mass. A nonempty subset ααalpha\alphaα of XXXXX is called compressible if for every nonempty open subset β⊆Xβ⊆Xbeta sube X\beta \subseteq Xβ⊆X there exists g∈Gg∈Gg in Gg \in Gg∈G with gα⊆βgα⊆βg alpha sube betag \alpha \subseteq \betagα⊆β. Obviously, if XXXXX is a minimal strongly proximal compact GGGGG-space and if GGGGG fixes a probability measure on XXXXX, then XXXXX is a singleton. Therefore, the following consequence of Theorem 3.3 is immediate.
Corollary 3.4. Let G∈RG∈RG inRG \in \mathscr{R}G∈R. If GGGGG is amenable, then LC(G)={0,∞}LC(G)={0,∞}LC(G)={0,oo}\mathscr{L} \mathscr{C}(G)=\{0, \infty\}LC(G)={0,∞}.
We now present another aspect of the local approach to the structure of simple tdlc groups. We define the local prime content of a tdlc group GGGGG, denoted by π(G)Ï€(G)pi(G)\pi(G)Ï€(G), to be the set of those primes ppppp such that every compact open subgroup U≤GU≤GU <= GU \leq GU≤G contains an infinite pro- ppppp subgroup.
Theorem 3.6 (See [28, TH. H] and [29, coR. 1.1.4 AND TH. 1.2.1]). The following assertions hold for any group G∈RG∈RG inRG \in \mathscr{R}G∈R :
(i) The local prime content π(G)Ï€(G)pi(G)\pi(G)Ï€(G) is finite and nonempty.
(ii) For each p∈π(G)p∈π(G)p in pi(G)p \in \pi(G)p∈π(G), there is a group G(p)∈RG(p)∈RG_((p))inRG_{(p)} \in \mathscr{R}G(p)∈R that is locally isomorphic to a pro-p group, and a dense embedding G(p)→GG(p)→GG_((p))rarr GG_{(p)} \rightarrow GG(p)→G.
(iii) If HHHHH is a tdlc group acting continuously and faithfully by automorphisms on GGGGG, then HHHHH is locally isomorphic to a pro- π(G)Ï€(G)pi(G)\pi(G)Ï€(G) group.
Roughly speaking, Theorem 3.6(ii) asserts that every group in RRR\mathscr{R}R can be "approximated" by a locally pro- ppppp group in RRR\mathscr{R}R. The restriction on the automorphism group of a group in RRR\mathscr{R}R from Theorem 3.6(iii) should be compared with the automorphism group of the restricted product M(p)M(p)M(p)M(p)M(p) from Example 2.2. Indeed, the Polish group Sym(Z)Symâ¡(Z)Sym(Z)\operatorname{Sym}(\mathbf{Z})Symâ¡(Z) embeds continuously in Aut(M(p))Autâ¡(M(p))Aut(M(p))\operatorname{Aut}(M(p))Autâ¡(M(p)) by permuting the simple factors, and every tdlcsc group continuously embeds in Sym(Z)Symâ¡(Z)Sym(Z)\operatorname{Sym}(\mathbf{Z})Symâ¡(Z). In some sense, the construction of stacking type chief factors in Example 2.3 crucially relies on the hugeness of the group Aut(M(p))Autâ¡(M(p))Aut(M(p))\operatorname{Aut}(M(p))Autâ¡(M(p)). Theorem 3.6(iii) shows that the automorphism group of a group in RRR\mathscr{R}R is considerably smaller.
Let us finish this subsection with a brief discussion of classification problems. The work of S. Smith [72] shows that Std Std S_("td ")\mathscr{S}_{\text {td }}Std contains uncountably many isomorphism classes; his methods of proof suggest that the isomorphism relation on Std Std S_("td ")\mathscr{S}_{\text {td }}Std has a similar complexity as the isomorphism relation on the class of finitely generated discrete simple groups. This provides evidence that the problem of classifying groups in Std Std S_("td ")\mathscr{S}_{\text {td }}Std up to isomorphism is illposed. The recent results on the local structure of groups in Std Std S_("td ")\mathscr{S}_{\text {td }}Std or in RRR\mathscr{R}R may be viewed as a hint to the fact the local isomorphism relation might be better behaved (see [29, тн. 1.1.5]). At the time of this writing, we do not know whether or not the groups in Std Std S_("td ")\mathscr{S}_{\text {td }}Std fall into countably many local isomorphism classes. However, classifying simple groups up to isomorphism remains a pertinent problem for some significant subclasses of Std Std S_("td ")\mathscr{S}_{\text {td }}Std . To wit, let us mention that, by [30, coR. 1.4], a group G∈Std G∈Std G inS_("td ")G \in \mathscr{S}_{\text {td }}G∈Std is isomorphic to a simple algebraic group over a local field if and only if it is locally isomorphic to a linear group, i.e., a subgroup of GLd(k)GLd(k)GL_(d)(k)\mathrm{GL}_{d}(k)GLd(k) for some integer ddddd and some locally compact field kkkkk. Lastly, a remarkable classification theorem concerning an important class of nonlinear simple groups acting on locally finite trees has been obtained by N. Radu [61]. It would be highly interesting to extend Radu's results by classifying all groups in Std Std S_("td ")\mathscr{S}_{\text {td }}Std acting properly and continuously by automorphisms on a given locally finite tree TTTTT in such a way that the action on the set of ends of TTTTT is doubly transitive. That class is denoted by STSTS_(T)\mathscr{S}_{T}ST. Results from [25] ensure that the isomorphism relation restricted to STSTS_(T)\mathscr{S}_{T}ST is smooth (see [37, DEFINITION 5.4.1]), which means that it comes at the bottom of the hierarchy of complexity of classification problems in the formalism established by invariant
not know whether there is a tree TTTTT such that STSTS_(T)\mathscr{S}_{T}ST contains uncountably many isomorphism classes.
3.2. Applications to lattices
The study of lattices in semisimple Lie and algebraic groups has known tremendous developments since the mid-20th century, with Margulis' seminal contributions as cornerstones. Remarkably, several key results on lattices have been established at a high level of generality, well beyond the realm of linear groups. An early illustration is provided by [13]. More recently, Y. Shalom [70] and Bader-Shalom [5] have established an extension of Margulis' Normal Subgroup Theorem valid for all irreducible cocompact lattices in products of groups in SSS\mathscr{S}S, while various analogues of Margulis' superrigidity for irreducible lattices in products have been established for various kinds of target spaces, see [3,4,31,36,38,55,56,70][3,4,31,36,38,55,56,70][3,4,31,36,38,55,56,70][3,4,31,36,38,55,56,70][3,4,31,36,38,55,56,70]. Those results have in common that they rely on transcendental methods: they use a mix
of tools from ergodic theory, probability theory, and abstract harmonic analysis, but do not require any detailed consideration of the algebraic structure of the ambient group. Another breakthrough in this field was accomplished by M. Burger and S. Mozes [15], who constructed a broad family of new finitely presented infinite simple groups as irreducible lattices in products of nonlinear groups in Std Std S_("td ")\mathscr{S}_{\text {td }}Std . Their seminal work involves a mix of transcendental methods together with a fair amount of structure theory developed in [14].
The following two recent results rely in an essential way on the properties of the class StdStdS_(td)\mathscr{S}_{\mathrm{td}}Std outlined above.
Theorem 3.7 (See [21, тн. A]). Let n≥2n≥2n >= 2n \geq 2n≥2 be an integer, let G1,…,Gn∈Std G1,…,Gn∈Std G_(1),dots,G_(n)inS_("td ")G_{1}, \ldots, G_{n} \in \mathscr{S}_{\text {td }}G1,…,Gn∈Std and Γ≤G=Γ≤G=Gamma <= G=\Gamma \leq G=Γ≤G=G1×⋯×GnG1×⋯×GnG_(1)xx cdots xxG_(n)G_{1} \times \cdots \times G_{n}G1×⋯×Gn be a lattice such that the projection pi(Γ)pi(Γ)p_(i)(Gamma)p_{i}(\Gamma)pi(Γ) is dense in GiGiG_(i)G_{i}Gi for all iiiii. Assume that ΓΓGamma\GammaΓ is cocompact, or that GGGGG has Kazhdan's property (T)(T)(T)(T)(T). Then the set of discrete subgroups of GGGGG containing ΓΓGamma\GammaΓ is finite.
Theorem 3.8 (See [21, тн. c]). Let n≥2n≥2n >= 2n \geq 2n≥2 be an integer and let G1,…,Gn∈StdG1,…,Gn∈StdG_(1),dots,G_(n)inS_(td)G_{1}, \ldots, G_{n} \in \mathscr{S}_{\mathrm{td}}G1,…,Gn∈Std be compactly presented. For every compact subset K⊂G=G1×⋯×GnK⊂G=G1×⋯×GnK sub G=G_(1)xx cdots xxG_(n)K \subset G=G_{1} \times \cdots \times G_{n}K⊂G=G1×⋯×Gn, the set of discrete subgroups Γ≤GΓ≤GGamma <= G\Gamma \leq GΓ≤G with G=KΓG=KΓG=K GammaG=K \GammaG=KΓ and with pi(Γ)pi(Γ)p_(i)(Gamma)p_{i}(\Gamma)pi(Γ) dense in GiGiG_(i)G_{i}Gi for all iiiii, is contained in a union of finitely many Aut(G)Autâ¡(G)Aut(G)\operatorname{Aut}(G)Autâ¡(G)-orbits.
For a detailed discussion of the notion of compactly presented locally compact groups, we refer to [32,cH.8[32,cH.8[32,cH.8[32, \mathbf{c H} .8[32,cH.8.
Theorems 3.7 and 3.8 can be viewed as respective analogues of two theorems of H. C. Wang [78,79][78,79][78,79][78,79][78,79] on lattices in semisimple Lie groups and reveal the existence of positive lower bounds on the covolume of certain families of irreducible cocompact lattices. It should be underlined that the corresponding statements fail for lattices in a single group G∈StdG∈StdG inS_(td)G \in \mathscr{S}_{\mathrm{td}}G∈Std, see [6, тн. 7.1]. Theorem 3.8 is established by combining Theorem 3.7 with recent results on local rigidity of cocompact lattices in arbitrary groups, due to Gelander-Levit [39].
3.3. Applications to commensurated subgroups
The structure theory of tdlc groups provides valuable tools in exploring the so-called commensurated subgroups of an abstract group. In this section, we recall that connection and illustrate it with several recent results. Further results on commensurated subgroups will be mentioned in Section 4 below.
Those commensurated subgroups are considered as trivial. For example, finite subgroups and subgroups of finite index are always commensurated subgroups. It is however important to underline that commensurated subgroups are not all of this trivial form. Indeed, an easy but crucial observation is that compact open subgroups are always commensurated. In particular, in the simple group PSL2(Qp)PSL2QpPSL_(2)(Q_(p))\mathrm{PSL}_{2}\left(\mathbf{Q}_{p}\right)PSL2(Qp), the subgroup PSL2(Zp)PSL2ZpPSL_(2)(Z_(p))\mathrm{PSL}_{2}\left(\mathbf{Z}_{p}\right)PSL2(Zp) (which is obviously not commensurate to any normal subgroup of PSL2(Qp)PSL2QpPSL_(2)(Q_(p))\mathrm{PSL}_{2}\left(\mathbf{Q}_{p}\right)PSL2(Qp) ) is commensurated.
Let us next remark that if UUUUU is a commensurated subgroup of a group GGGGG and φ:Γ→Gφ:Γ→Gvarphi:Gamma rarr G\varphi: \Gamma \rightarrow Gφ:Γ→G is a group homomorphism, then φ−1(U)φ−1(U)varphi^(-1)(U)\varphi^{-1}(U)φ−1(U) is a commensurated subgroup of ΓΓGamma\GammaΓ. This is the case in particular if GGGGG is a tdlc group and U≤GU≤GU <= GU \leq GU≤G is a compact open subgroup. A fundamental observation is that all commensurated subgroups of ΓΓGamma\GammaΓ arise in this way. More, precisely, a subgroup Λ≤ΓΛ≤ΓLambda <= Gamma\Lambda \leq \GammaΛ≤Γ is commensurated if and only if there is a tdlc group GGGGG, a compact open subgroup U≤GU≤GU <= GU \leq GU≤G, and a homomorphism φ:Γ→Gφ:Γ→Gvarphi:Gamma rarr G\varphi: \Gamma \rightarrow Gφ:Γ→G with dense image such that φ−1(U)=Λφ−1(U)=Λvarphi^(-1)(U)=Lambda\varphi^{-1}(U)=\Lambdaφ−1(U)=Λ. Indeed, given a commensurated subgroup Λ≤ΓΛ≤ΓLambda <= Gamma\Lambda \leq \GammaΛ≤Γ, then ΛΛLambda\LambdaΛ acts on the coset space Γ/ΛΓ/ΛGamma//Lambda\Gamma / \LambdaΓ/Λ with finite orbits, so that the closure of the natural image of ΓΓGamma\GammaΓ in the permutation group Sym(Γ/Λ)Symâ¡(Γ/Λ)Sym(Gamma//Lambda)\operatorname{Sym}(\Gamma / \Lambda)Symâ¡(Γ/Λ), endowed with the topology of pointwise convergence, is a tdlc group containing the closure of the image of ΛΛLambda\LambdaΛ as a compact open subgroup. That tdlc group is called the Schlichting completion of the pair (Γ,Λ)(Γ,Λ)(Gamma,Lambda)(\Gamma, \Lambda)(Γ,Λ), denoted by Γ//ΛΓ//ΛGamma////Lambda\Gamma / / \LambdaΓ//Λ. We refer to [68], [71, SECTION 3] and [65] for more information. Let us merely mention here that a commensurated subgroup Λ≤ΓΛ≤ΓLambda <= Gamma\Lambda \leq \GammaΛ≤Γ is commensurate to a normal subgroup if and only if the Schlichting completion G=Γ//ΛG=Γ//ΛG=Gamma////LambdaG=\Gamma / / \LambdaG=Γ//Λ is compact-by-discrete, i.e., GGGGG has a compact open normal subgroup (see [22, LEM. 5.1]).
The occurrence of nontrivial commensurated subgroups in finitely generated groups with few normal subgroups (e.g., simple groups, or just-infinite groups, i.e., groups all of whose proper quotients are finite) remains an intriguing phenomenon. On the empirical basis of the known examples, it seems to be rather rare. The following result provides valuable information in that context.
Theorem 3.9 (See [22, тн. 5.4]). Let ΓΓGamma\GammaΓ be a finitely generated group. Assume that all normal subgroups of ΓΓGamma\GammaΓ are finitely generated, and that every proper quotient of ΓΓGamma\GammaΓ is virtually nilpotent. Let also XXXXX be a compact ΓΓGamma\GammaΓ-space on which the ΓΓGamma\GammaΓ-action is faithful, minimal and microsupported. Assume that at least one of the following conditions is satisfied:
(1) ΓΓGamma\GammaΓ is residually finite.
(2) ΓΓGamma\GammaΓ fixes a probability measure on XXXXX.
Then every commensurated subgroup of ΓΓGamma\GammaΓ is commensurate to a normal subgroup.
This applies to all finitely generated branch groups, as well as to numerous finitely generated almost simple groups arising in Cantor dynamics, and whose study has known spectacular recent developments (see [34,59] and references therein). We refer to [22] for details and a more precise description of those applications.
Let us briefly outline how the proof of Theorem 3.9 works in the case where ΓΓGamma\GammaΓ fixes a probability measure on XXXXX. Let Λ≤ΓΛ≤ΓLambda <= Gamma\Lambda \leq \GammaΛ≤Γ be a commensurated subgroup and G=Γ//ΛG=Γ//ΛG=Gamma////LambdaG=\Gamma / / \LambdaG=Γ//Λ be the
corresponding Schlichting completion. That ΓΓGamma\GammaΓ is finitely generated implies that GGGGG is compactly generated. The hypotheses made on the normal subgroup structure of ΓΓGamma\GammaΓ yield some restrictions on the essentially chief series of GGGGG afforded by Theorem 2.1. More precisely, assuming by contradiction that ΛΛLambda\LambdaΛ is not commensurate to a normal subgroup, then the upper most chief factor K/LK/LK//LK / LK/L with trivial quasicenter in an essentially chief series for GGGGG must be compactly generated. Its structure is therefore described by Theorem 2.5. A key point in the proof, relying on various ingredients from topological dynamics and involving detailed considerations of the Chabauty space of closed subgroups of ΓΓGamma\GammaΓ and GGGGG, is to show that the given ΓΓGamma\GammaΓ-action on XXXXX gives rise to a continuous, faithful, microsupported G/LG/LG//LG / LG/L-action on a compact space YYYYY which is closely related to the original space XXXXX. Invoking (a suitable version of) Theorem 3.5 for the chief factor K/LK/LK//LK / LK/L ensures that YYYYY has a compressible open set, from which it follows that XXXXX has a compressible open set for the ΓΓGamma\GammaΓ-action. This finally contradicts the hypothesis of existence of a ΓΓGamma\GammaΓ-invariant probability measure.
4. SCALE METHODS
The scale of a tdlc group endomorphism, ααalpha\alphaα, is a positive integer that conveys information about the dynamics of the action of ααalpha\alphaα. Roughly speaking, ααalpha\alphaα contracts towards the identity on one subgroup of GGGGG and expands on another, and the scale is the expansion factor This section gives an account of properties of the scale and descriptions of the action of ααalpha\alphaα on certain associated subgroups of GGGGG which, when applied to inner automorphisms, answer questions about group structure.
Let α:G→Gα:G→Galpha:G rarr G\alpha: G \rightarrow Gα:G→G be a continuous endomorphism. The scale of ααalpha\alphaα is
Theorem 4.1. Let ααalpha\alphaα be a continuous endomorphism of the tdlc group GGGGG and let U≤GU≤GU <= GU \leq GU≤G be compact and open. Define subgroups
U+={u∈U∣∃{un}n≥0⊂U with u0=u and un=α(un+1)}U−={u∈U∣αn(u)∈U for all n≥0}.U+=u∈U∣∃unn≥0⊂U with u0=u and un=αun+1U−=u∈U∣αn(u)∈U for all n≥0.{:[U_(+)={u in U∣EE{u_(n)}_(n >= 0)sub U" with "u_(0)=u" and "u_(n)=alpha(u_(n+1))}],[U_(-)={u in U∣alpha^(n)(u)in U" for all "n >= 0}.]:}\begin{aligned}
& U_{+}=\left\{u \in U \mid \exists\left\{u_{n}\right\}_{n \geq 0} \subset U \text { with } u_{0}=u \text { and } u_{n}=\alpha\left(u_{n+1}\right)\right\} \\
& U_{-}=\left\{u \in U \mid \alpha^{n}(u) \in U \text { for all } n \geq 0\right\} .
\end{aligned}U+={u∈U∣∃{un}n≥0⊂U with u0=u and un=α(un+1)}U−={u∈U∣αn(u)∈U for all n≥0}.
Also define the subgroup U−−=⋃n≥0α−n(U−)U−−=⋃n≥0 α−nU−U_(--)=uuu_(n >= 0)alpha^(-n)(U_(-))U_{--}=\bigcup_{n \geq 0} \alpha^{-n}\left(U_{-}\right)U−−=⋃n≥0α−n(U−)of G.
Then UUUUU is minimizing for ααalpha\alphaα if and only if
Note that every compact open subgroup of GGGGG has a subgroup UUUUU for which TATATAT ATA holds and, if ααalpha\alphaα is the inner automorphism αg(x):=gxg−1αg(x):=gxg−1alpha_(g)(x):=gxg^(-1)\alpha_{g}(x):=g x g^{-1}αg(x):=gxg−1, then property TATATAT ATA implies that UgmUgnU=Ugm+nUUgmUgnU=Ugm+nUUg^(m)Ug^(n)U=Ug^(m+n)UU g^{m} U g^{n} U=U g^{m+n} UUgmUgnU=Ugm+nU for all m,n≥0m,n≥0m,n >= 0m, n \geq 0m,n≥0. These points were already used in [12] in the proof that a reductive group over a locally compact field of positive characteristic is type I, where they were observed to hold in such groups.
In the following compilation of results from [54,85,86,89],Δ[54,85,86,89],Δ[54,85,86,89],Delta[54,85,86,89], \Delta[54,85,86,89],Δ denotes the modular function on the automorphism group of GGGGG.
Theorem 4.2. The scale s:End(G)→Z+s:Endâ¡(G)→Z+s:End(G)rarrZ^(+)s: \operatorname{End}(G) \rightarrow \mathbb{Z}^{+}s:Endâ¡(G)→Z+satisfies:
(i) s(α)=1s(α)=1quad s(alpha)=1\quad s(\alpha)=1s(α)=1 if and only if there is a compact open subgroup U≤GU≤GU <= GU \leq GU≤G with α(U)≤Uα(U)≤Ualpha(U) <= U\alpha(U) \leq Uα(U)≤U;
(iii) if ααalpha\alphaα is an automorphism, then Δ(α)=s(α)/s(α−1)Δ(α)=s(α)/sα−1Delta(alpha)=s(alpha)//s(alpha^(-1))\Delta(\alpha)=s(\alpha) / s\left(\alpha^{-1}\right)Δ(α)=s(α)/s(α−1).
The function s∘α∙:G→Z+s∘α∙:G→Z+s@alpha_(∙):G rarrZ^(+)s \circ \alpha_{\bullet}: G \rightarrow \mathbb{Z}^{+}s∘α∙:G→Z+, with αg(x)=gxg−1αg(x)=gxg−1alpha_(g)(x)=gxg^(-1)\alpha_{g}(x)=g x g^{-1}αg(x)=gxg−1, is continuous for the group topology on GGGGG and the discrete topology on Z+Z+Z^(+)\mathbb{Z}^{+}Z+.
Continuity of s∘α∙s∘α∙s@alpha_(∙)s \circ \alpha_{\bullet}s∘α∙ is implied by the fact that, if UUUUU is tidy for ggggg, then UUUUU is also tidy for all h∈UgUh∈UgUh in UgUh \in U g Uh∈UgU and s(h)=s(g)s(h)=s(g)s(h)=s(g)s(h)=s(g)s(h)=s(g), [85, THEOREM 3].
Subgroups of GGGGG defined in terms of the action of ααalpha\alphaα are related to the scale and tidy subgroups. It is convenient to confine the statements to automorphisms here. Extensions to endomorphisms may be found in [16,89][16,89][16,89][16,89][16,89].
The contraction subgroup for α∈Aut(G)α∈Autâ¡(G)alpha in Aut(G)\alpha \in \operatorname{Aut}(G)α∈Autâ¡(G) is
con(α)={x∈G∣αn(x)→1 as n→∞}conâ¡(α)=x∈G∣αn(x)→1 as n→∞con(alpha)={x in G∣alpha^(n)(x)rarr1" as "n rarr oo}\operatorname{con}(\alpha)=\left\{x \in G \mid \alpha^{n}(x) \rightarrow 1 \text { as } n \rightarrow \infty\right\}conâ¡(α)={x∈G∣αn(x)→1 as n→∞}
The next result, from [9,46][9,46][9,46][9,46][9,46], relates contraction subgroups to the scale.
Theorem 4.3. Let α∈Aut(G)α∈Autâ¡(G)alpha in Aut(G)\alpha \in \operatorname{Aut}(G)α∈Autâ¡(G). Then ⋂{U−−∣Uâ‹‚U−−∣Unnn{U_(--)∣U:}\bigcap\left\{U_{--} \mid U\right.â‹‚{U−−∣U is tidy for α}α{: alpha}\left.\alpha\right\}α} is equal to con(α)¯conâ¡(α)¯bar(con(alpha))\overline{\operatorname{con}(\alpha)}conâ¡(α)¯, and s(α−1)sα−1s(alpha^(-1))s\left(\alpha^{-1}\right)s(α−1) is equal to the scale of the restriction of α−1α−1alpha^(-1)\alpha^{-1}α−1 to con(α)¯conâ¡(α)¯bar(con(alpha))\overline{\operatorname{con}(\alpha)}conâ¡(α)¯. Hence s(α−1)>1sα−1>1s(alpha^(-1)) > 1s\left(\alpha^{-1}\right)>1s(α−1)>1 if and only if con(α)¯conâ¡(α)¯bar(con(alpha))\overline{\operatorname{con}(\alpha)}conâ¡(α)¯ is not compact.
If GGGGG is a ppppp-adic Lie group, then con(α)conâ¡(α)con(alpha)\operatorname{con}(\alpha)conâ¡(α) is closed for every ααalpha\alphaα, [80], but that is not the case if, for example, GGGGG is the isometry group of a regular tree, or a certain type of complete Kac-Moody group [7], or if LE(G)≠{0,∞}LE(G)≠{0,∞}LE(G)!={0,oo}\mathscr{L} \mathscr{E}(G) \neq\{0, \infty\}LE(G)≠{0,∞} [28]. The closedness of con (α)(α)(alpha)(\alpha)(α) is equivalent, by [9, THEOREM 3.32], to the triviality of the nubnubnubn u bnub subgroup,
nub(α)=⋂{U∣U tidy for α}nubâ¡(α)=â‹‚{U∣U tidy for α}nub(alpha)=nnn{U∣U" tidy for "alpha}\operatorname{nub}(\alpha)=\bigcap\{U \mid U \text { tidy for } \alpha\}nubâ¡(α)=â‹‚{U∣U tidy for α}
The nub for ααalpha\alphaα is compact and is the largest ααalpha\alphaα-stable subgroup of GGGGG on which ααalpha\alphaα acts ergodically, which sharpens the theorem of N. Aoki in [2] that a totally disconnected locally compact group with an ergodic automorphism must be compact. P. Halmos had asked in [44] whether that was so for all locally compact groups. See [48,90] for the connected case, and also [60].
The structure of closed contraction subgroups con (α)(α)(alpha)(\alpha)(α) is described precisely in [40] If con(α)conâ¡(α)con(alpha)\operatorname{con}(\alpha)conâ¡(α) is closed, there is a composition series
of ααalpha\alphaα-stable closed subgroups of con(α)conâ¡(α)con(alpha)\operatorname{con}(\alpha)conâ¡(α) such that the factors Gi+1/GiGi+1/GiG_(i+1)//G_(i)G_{i+1} / G_{i}Gi+1/Gi have no proper, nontrivial ααalpha\alphaα-stable closed subgroups. The factors appearing in any such series are unique up to permutation and isomorphism, and their isomorphism types come from a countable list: each torsion factor being a restricted product ⨁i∈Z(Gi,Ui)â¨i∈Z Gi,Uibigoplus_(i inZ)(G_(i),U_(i))\bigoplus_{i \in \mathbf{Z}}\left(G_{i}, U_{i}\right)â¨i∈Z(Gi,Ui) with Gi=FGi=FG_(i)=FG_{i}=FGi=F, a finite simple group, and Ui=FUi=FU_(i)=FU_{i}=FUi=F if i≥0i≥0i >= 0i \geq 0i≥0 and trivial if i<0i<0i < 0i<0i<0, and the automorphism the shift; and each divisible factor being a ppppp-adic vector group and the automorphism a linear transformation. Moreover, con (α)(α)(alpha)(\alpha)(α) is the direct product T×DT×DT xx DT \times DT×D with TTTTT a torsion and DDDDD a divisible ααalpha\alphaα-stable subgroup. The divisible subgroup DDDDD is a direct product Dp1×⋯×DprDp1×⋯×DprD_(p_(1))xx cdots xxD_(p_(r))D_{p_{1}} \times \cdots \times D_{p_{r}}Dp1×⋯×Dpr with DpiDpiD_(p_(i))D_{p_{i}}Dpi a nilpotent ppppp-adic Lie group for each pipip_(i)p_{i}pi. The torsion group TTTTT may include nonabelian irreducible factors but, should it happen to be locally pro- ppppp, then it is nilpotent too, see [42]. The number of nonisomorphic locally pro- ppppp closed contraction groups is uncountable [41].
Contraction groups correspond to unipotent subgroups of algebraic groups and, following [75], the Tits core, G†G†G^(†)G^{\dagger}G†, of the tdlc group GGGGG is defined to be the subgroup generated by all closures of contraction groups. It is shown in [26] that, if GGGGG is topologically simple, then G†G†G^(†)G^{\dagger}G†is either trivial or is abstractly simple and dense in GGGGG.
The correspondence with algebraic groups is pursued in [9], where the parabolic subgroup for α∈Aut(G)α∈Autâ¡(G)alpha in Aut(G)\alpha \in \operatorname{Aut}(G)α∈Autâ¡(G) is defined to be
par(α)={x∈G∣{αn(x)}n≥0 has compact closure }parâ¡(α)=x∈G∣αn(x)n≥0 has compact closure par(alpha)={x in G∣{alpha^(n)(x)}_(n >= 0)" has compact closure "}\operatorname{par}(\alpha)=\left\{x \in G \mid\left\{\alpha^{n}(x)\right\}_{n \geq 0} \text { has compact closure }\right\}parâ¡(α)={x∈G∣{αn(x)}n≥0 has compact closure }
A group, HHH\mathscr{H}H, of automorphisms of GGGGG is flat if there is a compact open subgroup, U≤GU≤GU <= GU \leq GU≤G, that is tidy for every α∈Hα∈Halpha inH\alpha \in \mathscr{H}α∈H. The stabilizer of UUUUU in HHH\mathscr{H}H is called the uniscalar subgroup and denoted HuHuH_(u)\mathscr{H}_{u}Hu. The factoring of subgroups tidy for a single automorphism in Theorem 4.1 extends to flat groups as follows.
Theorem 4.4 ([87]). Let HHH\mathscr{H}H be a finitely generated flat group of automorphisms of GGGGG and suppose that UUUUU is tidy for HHH\mathscr{H}H. Then Hu◃HHuâ—ƒHH_(u)â—ƒH\mathscr{H}_{u} \triangleleft \mathscr{H}Huâ—ƒH and there is r≥0r≥0r >= 0r \geq 0r≥0 such that
There are q≥0q≥0q >= 0q \geq 0q≥0 and closed groups Uj≤U,j∈{0,1,…,q}Uj≤U,j∈{0,1,…,q}U_(j) <= U,j in{0,1,dots,q}U_{j} \leq U, j \in\{0,1, \ldots, q\}Uj≤U,j∈{0,1,…,q} such that α(U0)=U0;α(Uj)αU0=U0;αUjalpha(U_(0))=U_(0);alpha(U_(j))\alpha\left(U_{0}\right)=U_{0} ; \alpha\left(U_{j}\right)α(U0)=U0;α(Uj) is either a subgroup or supergroup of UjUjU_(j)U_{j}Uj for every j∈{1,…,q}j∈{1,…,q}j in{1,dots,q}j \in\{1, \ldots, q\}j∈{1,…,q}; and U=U0U1⋯UqU=U0U1⋯UqU=U_(0)U_(1)cdotsU_(q)U=U_{0} U_{1} \cdots U_{q}U=U0U1⋯Uq.
U~j:=⋃α∈Hα(Uj)U~j:=⋃α∈H αUjtilde(U)_(j):=uuu_(alpha inH)alpha(U_(j))\tilde{U}_{j}:=\bigcup_{\alpha \in \mathscr{H}} \alpha\left(U_{j}\right)U~j:=⋃α∈Hα(Uj) is a closed subgroup of G for each j∈{1,…,q}j∈{1,…,q}j in{1,dots,q}j \in\{1, \ldots, q\}j∈{1,…,q}.
There are, for each j∈{1,…,q}j∈{1,…,q}j in{1,dots,q}j \in\{1, \ldots, q\}j∈{1,…,q}, an integer sj>1sj>1s_(j) > 1s_{j}>1sj>1 and a surjective homomorphism ρj:H→(Z,+)Ïj:H→(Z,+)rho_(j):Hrarr(Z,+)\rho_{j}: \mathscr{H} \rightarrow(\mathbb{Z},+)Ïj:H→(Z,+) such that Δ(α|U~j)=sjρj(α)ΔαU~j=sjÏj(α)Delta( alpha|_( tilde(U)_(j)))=s_(j)^(rho_(j)(alpha))\Delta\left(\left.\alpha\right|_{\tilde{U}_{j}}\right)=s_{j}^{\rho_{j}(\alpha)}Δ(α|U~j)=sjÏj(α).
The integers rrrrr and qqqqq, and integers sjsjs_(j)s_{j}sj and homomorphisms ρjÏjrho_(j)\rho_{j}Ïj for each j∈{1,…,q}j∈{1,…,q}j in{1,dots,q}j \in\{1, \ldots, q\}j∈{1,…,q}, are independent of the subgroup UUUUU tidy for HHH\mathscr{H}H.
More generally, flatness of groups of automorphisms may be shown by the following converse to the fact that flat groups are abelian modulo the stablizer of tidy subgroups.
Theorem 4.5 ([87][71]). Every finitely generated nilpotent subgroup of Aut(G)Autâ¡(G)Aut(G)\operatorname{Aut}(G)Autâ¡(G) is flat, and every polycyclic subgroup is virtually flat.
Flatness is used-in combination with bounded generation of arithmetic groups [57,74], the fact that almost normal subgroups are close to normal [11], and the Margulis normal subgroup theorem [53]-to prove the Margulis-Zimmer conjecture in the special case of Chevalley groups in [71] and show that there are no commensurated subgroups of arithmetic subgroups other than the natural ones.
5. FUTURE DIRECTIONS
The contributions to the structure theory of tdlc groups surveyed in this article highlight that, for a general tdlc group GGGGG, as soon as the topology is nondiscrete, its interaction with the group structure yields significant algebraic constraints. As mentioned in the introduction, we view the dynamics of the conjugation action as a unifying theme of our considerations. The results we have surveyed reveal that those dynamics tend to be richer
than one might expect. This is especially the case among tdlc groups that are nonelementary. We hope that further advances will shed more light on this paradigm in the future.
Concerning decomposition theory, it is an important open problem to clarify what distinguishes elementary and nonelementary tdlc groups. A key question asks whether every nonelementary tdlcsc group GGGGG contains a closed subgroup HHHHH admitting a quotient in Std Std S_("td ")\mathscr{S}_{\text {td }}Std . Concerning simple groups, our results yield a dichotomy, depending on whether the centralizer lattice is trivial or not. The huge majority of known examples of groups in Std Std S_("td ")\mathscr{S}_{\text {td }}Std (listed in [28, APPENDIX A]) have a nontrivial centralizer lattice, the most notable exceptions being the simple algebraic groups over local fields. Finding new groups in StdStdS_(td)\mathscr{S}_{\mathrm{td}}Std with a trivial centralizer lattice would be a decisive step forward. A fundamental source of examples of tdlc groups is provided by Galois groups of transcendental field extensions with finite transcendence degree (see [66, TH. 2.9], highlighting the occurrence of topologically simple groups), but this territory remains largely unexplored from the viewpoint of structure theory of tdlc groups. Concerning scale methods, the structure of tdlc groups all of whose elements are uniscalar (i.e., have scale 1) is still mysterious. In particular, we do not know whether every such group is elementary. This is equivalent to asking whether a tdlc group, all of whose closed subgroups are unimodular, is necessarily elementary. A positive answer would provide a formal incarnation to the claim that the dynamics of the conjugation action is nontrivial for all nonelementary tdlc groups. We refer to [24] for a more extensive list of specific problems.
We believe that a good measurement of the maturity of a mathematical theory is provided by its ability to solve problems arising on the outside of the theory. For the structure theory of tdlc groups, the Margulis-Zimmer conjecture appears as a natural target. As mentioned in Section 4, partial results in the nonuniform case, relying on scale methods on tdlc groups, have already been obtained in [71].
Another source of external problems is provided by abstract harmonic analysis. As mentioned in the introduction, the emergence of locally compact groups as an independent subject of study coincides with the foundation of abstract harmonic analysis. However, fundamental problems clarifying the links between the algebraic structure of a locally compact group and the properties of its unitary representations remain open. The class of amenable locally compact groups is defined by a representation theoretic property (indeed, a locally compact group is amenable if and only if every unitary representation is weakly contained in the regular), but purely algebraic characterizations of amenable groups are still missing. In particular, the following nondiscrete version of Day's problem is open and intriguing: Is every amenable second countable tdlc group elementary (in the sense of Section 2)? The unitary representation theory also reveals a fundamental dichotomy between locally compact groups of type IIIII (roughly speaking, those for which the problem of classifying the irreducible unitary representations up to equivalence is tractable) and the others (see [10,35,52][10,35,52][10,35,52][10,35,52][10,35,52] ). Algebraic characterizations of type I groups are also desirable. In particular, we underline the following question: Does every second countable locally compact group of type I contain a cocompact amenable subgroup? For a more detailed discussion of that problem and related results, we refer to [20].
ACKNOWLEDGMENTS
It is a pleasure to take this opportunity to heartily thank our collaborators, past and present, for their ideas and companionship. We are grateful to Adrien Le Boudec and Colin Reid for their comments on a preliminary version of this article.
FUNDING
This work was written while P.-E. Caprace was a Senior Research Associate of the Belgian F.R.S.-FNRS and G. A. Willis was Australian Research Council Laureate Professor under the grant FL170100032. The support of these bodies is gratefully acknowledged.
REFERENCES
[1] H. Abels, Specker-Kompaktifizierungen von lokal kompakten topologischen Gruppen. Math. Z. 135 (1973/1974), 325-361.
[2] N. Aoki, Dense orbits of automorphisms and compactness of groups. Topology Appl. 20 (1985), no. 1, 1-15.
[3] U. Bader and A. Furman, Boundaries, Weyl groups, and superrigidity. Electron. Res. Announc. Math. Sci. 19 (2012), 41-48.
[4] U. Bader and A. Furman, Boundaries, rigidity of representations, and Lyapunov exponents. In Proceedings of the International Congress of MathematiciansSeoul 2014. Vol. III, pp. 71-96, Kyung Moon Sa, Seoul, 2014.
[5] U. Bader and Y. Shalom, Factor and normal subgroup theorems for lattices in products of groups. Invent. Math. 163 (2006), no. 2, 415-454.
[6] H. Bass and R. Kulkarni, Uniform tree lattices. J. Amer. Math. Soc. 3 (1990), no. 4, 843-902.
[9] U. Baumgartner and G. A. Willis, Contraction groups and scales of automorphisms of totally disconnected locally compact groups. Israel J. Math. 142 (2004), 221-248.
[10] B. Bekka and P. de la Harpe, Unitary representations of groups, duals, and characters. Math. Surveys Monogr. 250, American Mathematical Society, Providence, RI, 2020.
[11] G. M. Bergman and H. W. Lenstra Jr., Subgroups close to normal subgroups. J. Algebra 127 (1989), no. 1, 80-97.
[12] I. N. BernÅ¡teÄn, All reductive ppp\mathfrak{p}p-adic groups are of type I. Funktsional. Anal. i Prilozhen. 8 (1974), no. 2, 3-6.
[13] I. N. BernÅ¡teÄn and D. A. Každan, The one-dimensional cohomology of discrete subgroups. Funktsional. Anal. i Prilozhen. 4 (1970), no. 1, 1-5.
[14] M. Burger and S. Mozes, Groups acting on trees: from local to global structure. Publ. Math. Inst. Hautes Études Sci. 92 (2000), 113-150.
[15] M. Burger and S. Mozes, Lattices in product of trees. Publ. Math. Inst. Hautes Études Sci. 92 (2000), 151-194.
[16] T. P. Bywaters, H. Glöckner, and S. Tornier, Contraction groups and passage to subgroups and quotients for endomorphisms of totally disconnected locally compact groups. Israel J. Math. 227 (2018), 691-752.
[17] P.-E. Caprace, Non-discrete simple locally compact groups. In European Congress of Mathematics, pp. 333-354, Eur. Math. Soc., Zürich, 2018.
[18] P.-E. Caprace, Y. Cornulier, N. Monod, and R. Tessera, Amenable hyperbolic groups. J. Eur. Math. Soc. (JEMS) 17 (2015), no. 11, 2903-2947.
[19] P.-E. Caprace and T. De, Medts, Simple locally compact groups acting on trees and their germs of automorphisms. Transform. Groups 16 (2011), no. 2, 375-411.
[20] P.-E. Caprace, M. Kalantar, and N. Monod, A type I conjecture and boundary representations of hyperbolic groups. 2021, arXiv:2110.00190.
[21] P.-E. Caprace and A. Le Boudec, Bounding the covolume of lattices in products. Compos. Math. 155 (2019), no. 12, 2296-2333.
[22] P.-E. Caprace, A. Le Boudec, and D. Francoeur, Commensurated subgroups and micro-supported actions. 2020, arXiv:2002.02910. To appear in J. Eur. Math. Soc. (JEMS).
[23] P.-E. Caprace and N. Monod, Decomposing locally compact groups into simple pieces. Math. Proc. Cambridge Philos. Soc. 150 (2011), no. 1, 97-128.
[24] P.-E. Caprace and N. Monod, Future directions in locally compact groups: a tentative problem list. In New directions in locally compact groups, pp. 343-355, London Math. Soc. Lecture Note Ser. 447, Cambridge Univ. Press, Cambridge, 2018.
[25] P.-E. Caprace and N. Radu, Chabauty limits of simple groups acting on trees. J. Inst. Math. Jussieu 19 (2020), no. 4, 1093-1120.
[26] P.-E. Caprace, C. D. Reid, and G. A. Willis, Limits of contraction groups and the Tits core. J. Lie Theory 24 (2014), 957-967.
[27] P.-E. Caprace, C. D. Reid, and G. A. Willis, Locally normal subgroups of totally disconnected groups. Part I: general theory. Forum Math. Sigma 5 (2017), e11, 76.
[28] P.-E. Caprace, C. D. Reid, and G. A. Willis, Locally normal subgroups of totally disconnected groups. Part II: compactly generated simple groups. Forum Math. Sigma 5 (2017), e12, 89.
[29] P.-E. Caprace, C. Reid, and P. Wesolek, Approximating simple locally compact groups by their dense locally compact subgroups. Int. Math. Res. Not. IMRN 7 (2021), 5037-5110.
[30] P.-E. Caprace and T. Stulemeijer, Totally disconnected locally compact groups with a linear open subgroup. Int. Math. Res. Not. IMRN 24 (2015), 13800-13829.
[31] I. Chatterji, T. Fernós, and A. Iozzi, The median class and superrigidity of actions on CAT(0) cube complexes. J. Topol. 9 (2016), no. 2, 349-400.
[32] Y. Cornulier and P. de la Harpe, Metric geometry of locally compact groups. EMS Tracts Math. 25, European Mathematical Society (EMS), Zürich, 2016.
[33] M. M. Day, Amenable semigroups. Illinois J. Math. 1 (1957), 509-544.
[36] E. Fioravanti, Superrigidity of actions on finite rank median spaces. Adv. Math. 352 (2019), 1206-1252.
[37] S. Gao, Invariant descriptive set theory. Pure Appl. Math. (Boca Raton) 293, CRC Press, Boca Raton, FL, 2009.
[38] T. Gelander, A. Karlsson, and G. A. Margulis, Superrigidity, generalized harmonic maps and uniformly convex spaces. Geom. Funct. Anal. 17 (2008), no. 5, 1524−15501524−15501524-15501524-15501524−1550.
[39] T. Gelander and A. Levit, Local rigidity of uniform lattices. Comment. Math. Helv. 93 (2018), no. 4, 781-827.
[40] H. Glöckner and G. A. Willis, Classification of the simple factors appearing in composition series of totally disconnected contraction groups. J. Reine Angew. Math. 643 (2010), 141-169.
[41] H. Glöckner and G. A. Willis, Decompositions of locally compact contraction groups, series and extensions. J. Algebra 570 (2021), 164-214.
[42] H. Glöckner and G. A. Willis, Locally pro- ppppp contraction groups are nilpotent. J. Reine Angew. Math. (2021). DOI 10.1515/crelle-2021-0050.
[43] R. Guralnick, Applications of the classification of finite simple groups. In Proceedings of the International Congress of Mathematicians-Seoul 2014. Vol. II, pp. 163-177, Kyung Moon Sa, Seoul, 2014.
[44] P. R. Halmos, Lectures on ergodic theory. Publ. Math. Soc Jpn. 3, The Mathematical Society of Japan, 1956.
[45] K. H. Hofmann and A. Mukherjea, Concentration functions and a class of noncompact groups. Math. Ann. 256 (1981), no. 4, 535-548.
[46] W. Jaworski, On contraction groups of automorphisms of totally disconnected locally compact groups. Israel J. Math. 172 (2009), 1-8.
[47] W. Jaworski, J. Rosenblatt, and G. A. Willis, Concentration functions in locally compact groups. Math. Ann. 305 (1996), no. 4, 673-691.
[48] R. Kaufman and M. Rajagopalan, On automorphisms of a locally compact group. Michigan Math. J. 13 (1966), 373-374.
[49] V. Lafforgue, Shtukas for reductive groups and Langlands correspondence for function fields. In Proceedings of the International Congress of MathematiciansRio de Janeiro 2018. I. Plenary lectures, pp. 635-668, World Sci. Publ., Hackensack, NJ, 2018.
[50] A. Le Boudec, Groups acting on trees with almost prescribed local action. Comment. Math. Helv. 91 (2016), no. 2, 253-293.
[51] G. W. Mackey, On induced representations of groups. Amer. J. Math. 73 (1951), 576−592576−592576-592576-592576−592.
[52] G. W. Mackey, The theory of unitary group representations. Chicago Lectures in Math., University of Chicago Press, Chicago, IL-London, 1976.
[53] G. A. Margulis, Discrete subgroups of semisimple Lie groups. Ergeb. Math. Grenzgeb. (3) [Res. Math. Related Areas (3)] 17, Springer, Berlin, 1991.
[54] R. G. Möller, Structure theory of totally disconnected locally compact groups via graphs and permutations. Canad. J. Math. 54 (2002), 795-827.
[55] N. Monod, Superrigidity for irreducible lattices and geometric splitting. J. Amer Math. Soc. 19 (2006), no. 4, 781-814.
[56] N. Monod and Y. Shalom, Cocycle superrigidity and bounded cohomology for negatively curved spaces. J. Differential Geom. 67 (2004), no. 3, 395-455.
[57] D. W. Morris, Bounded generation of SL(n,A)SL(n,A)SL(n,A)S L(n, A)SL(n,A). New York J. Math. 13 (2007), 383-421.
[58] V. Nekrashevych, Self-similar groups. Math. Surveys Monogr. 117, American Mathematical Society, Providence, RI, 2005.
[59] V. Nekrashevych, Simple groups of dynamical origin. Ergodic Theory Dynam. Systems 39 (2019), no. 3, 707-732.
[60] W. H. Previts and T. S. Wu, Dense orbits and compactness of groups. Bull. Aust. Math. Soc. 68 (2003), no. 1, 155-159.
[61] N. Radu, A classification theorem for boundary 2-transitive automorphism groups of trees. Invent. Math. 209 (2017), no. 1, 1-60.
[62] C. D. Reid, Normal subgroup structure of totally disconnected locally compact groups. In 2016 MATRIX Annals, pp. 525-560, MATRIX Book Ser. 1, Springer, Cham, 2018.
[63] C. D. Reid and P. R. Wesolek, Dense normal subgroups and chief factors in locally compact groups. Proc. Lond. Math. Soc. (3) 116 (2018), no. 4, 760-812.
[64] C. D. Reid and P. R. Wesolek, The essentially chief series of a compactly generated locally compact group. Math. Ann. 370 (2018), no. 1-2, 841-861.
[65] C. D. Reid and P. R. Wesolek, Homomorphisms into totally disconnected, locally compact groups with dense image. Forum Math. 31 (2019), no. 3, 685-701.
[66] M. Rovinsky, Motives and admissible representations of automorphism groups of fields. Math. Z. 249 (2005), no. 1, 163-221.
[67] M. Rubin, Locally moving groups and reconstruction problems. In Ordered groups and infinite permutation groups, pp. 121-157, Math. Appl. 354, Kluwer Acad. Publ., Dordrecht, 1996.
[68] G. Schlichting, Operationen mit periodischen Stabilisatoren. Arch. Math. (Basel) 34 (1980), no. 2, 97-99.
[69] P. Scholze, p-adic geometry. In Proceedings of the International Congress of Mathematicians-Rio de Janeiro 2018. I. Plenary lectures, pp. 899-933, World Sci. Publ., Hackensack, NJ, 2018.
[70] Y. Shalom, Rigidity of commensurators and irreducible lattices. Invent. Math. 141 (2000), no. 1, 1-54.
[71] Y. Shalom and G. A. Willis, Commensurated subgroups of arithmetic groups, totally disconnected groups and adelic rigidity. Geom. Funct. Anal. 23 (2013), no. 5, 1631-1683.
[72] S. M. Smith, A product for permutation groups and topological groups. Duke Math. J. 166 (2017), no. 15, 2965-2999.
[73] T. Tao, Hilbert's fifth problem and related topics. Grad. Stud. Math. 153, American Mathematical Society, Providence, RI, 2014.
[74] O. I. Tavgen, Bounded generability of Chevalley groups over rings of sssss-integer algebraic numbers. Izv. Akad. Nauk SSSR Ser. Mat. 54 (1990), no. 1, 97-122, 221-222.
[75] J. Tits, Algebraic and abstract simple groups. Ann. of Math. (2) 80 (1964), 313-329.
[82] P. Wesolek, Elementary totally disconnected locally compact groups. Proc. Lond. Math. Soc. (3) 110 (2015), no. 6, 1387-1434.
[83] P. Wesolek, A survey of elementary totally disconnected locally compact groups. In 2016 MATRIX Annals, pp. 593-611, MATRIX Book Ser. 1, Springer, Cham, 2018.
[84] G. Willis, Totally disconnected groups and proofs of conjectures of Hofmann and Mukherjea. Bull. Aust. Math. Soc. 51 (1995), no. 3, 489-494.
[85] G. A. Willis, The structure of totally disconnected, locally compact groups. Math. Ann. 300 (1994), no. 2, 341-363.
[86] G. A. Willis, Further properties of the scale function on a totally disconnected group. J. Algebra 237 (2001), no. 1, 142-164.
[87] G. A. Willis, Tidy subgroups for commuting automorphisms of totally disconnected groups: an analogue of simultaneous triangularisation of matrices. New York J. Math. 10 (2004), 1-35.
[88] G. A. Willis, Compact open subgroups in simple totally disconnected groups. J. Algebra 312 (2007), no. 1, 405-417.
[89] G. A. Willis, The scale and tidy subgroups for endomorphisms of totally disconnected locally compact groups. Math. Ann. 361 (2015), no. 1-2, 403-442.
[90] T. S. Wu, Continuous automorphisms on locally compact groups. Math. Z. 96 (1967), 256-258.
University of Newcastle, Callaghan 2308, Australia, george.willis @ newcastle.edu.au
THE ZARISKI
CANCELLATION PROBLEM AND RELATED PROBLEMS IN AFFINE ALGEBRAIC GEOMETRY
NEENA GUPTA
ABSTRACT
In this article, we shall discuss the solution to the Zarsiki Cancellation Problem in positive characteristic, various approaches taken so far towards the possible solution in characteristic zero, and several other questions related to this problem.
Right from the beginning of the 19th century, mathematicians have been involved in studying polynomial rings (over CCC\mathbb{C}C and over RRR\mathbb{R}R ). Some of the early breakthroughs on polynomial rings have led to the foundation of Commutative Algebra. One such result is the Hilbert Basis Theorem, a landmark result on the finite generation of ideals, which solved a central problem on invariant theory. This was followed by the Hilbert Nullstellensatz which connects affine varieties (zero locus of a set of polynomials) with rings of regular functions on varieties and thus enables one to make use of the algebraic machinery of commutative algebra to study geometric properties of varieties.
Affine Algebraic Geometry deals with the study of affine spaces (and certain closed subspaces), equivalently, polynomial rings (and certain quotients). There are many fundamental problems on polynomial rings which can be formulated in an elementary mathematical language but whose solutions remain elusive. Any significant progress requires the development of new and powerful methods and their ingenious applications.
One of the most challenging problems in Affine Algebraic Geometry is the Zariski Cancelation Problem (ZCP) on polynomial rings (Question 1' below). In this article, we shall discuss the solution to the ZCP in positive characteristic, various approaches taken so far towards the possible solution in characteristic zero, and several other questions related to this problem. For a survey on problems in Affine Algebraic Geometry, one may look at [42,62,69][42,62,69][42,62,69][42,62,69][42,62,69].
Throughout the article, all rings will be assumed to be commutative with unity and kkkkk will denote a field. For a ring R,R∗R,R∗R,R^(**)R, R^{*}R,R∗ will denote the group of units of RRRRR. We shall use the notation R[n]R[n]R^([n])R^{[n]}R[n] for a polynomial ring in nnnnn variables over a commutative ring RRRRR. Thus, E=R[n]E=R[n]E=R^([n])E=R^{[n]}E=R[n] will mean that E=R[t1,…,tn]E=Rt1,…,tnE=R[t_(1),dots,t_(n)]E=R\left[t_{1}, \ldots, t_{n}\right]E=R[t1,…,tn] for some elements t1,…,tnt1,…,tnt_(1),dots,t_(n)t_{1}, \ldots, t_{n}t1,…,tn in EEEEE which are algebraically independent over RRRRR. Unless otherwise stated, capital letters like X1,X2,…,Xn,Y1,…,Ym,X,Y,Z,TX1,X2,…,Xn,Y1,…,Ym,X,Y,Z,TX_(1),X_(2),dots,X_(n),Y_(1),dots,Y_(m),X,Y,Z,TX_{1}, X_{2}, \ldots, X_{n}, Y_{1}, \ldots, Y_{m}, X, Y, Z, TX1,X2,…,Xn,Y1,…,Ym,X,Y,Z,T will be used as variables of polynomial rings.
2. CANCELLATION PROBLEM
Let AAAAA be an affine (finitely generated) algebra over a field kkkkk. The kkkkk-algebra AAA\mathrm{A}A is said to be cancellative (over kkkkk ) if, for any kkkkk-algebra B,A[X]≅kB[X]B,A[X]≅kB[X]B,A[X]~=_(k)B[X]B, A[X] \cong_{k} B[X]B,A[X]≅kB[X] implies that A≅kBA≅kBA~=_(k)BA \cong_{k} BA≅kB. A natural question in this regard is: which affine domains are cancellative? More precisely:
Question 1. Let AAAAA be an affine algebra over a field kkkkk. Suppose that BBBBB is a kkkkk-algebra such that the polynomial rings A[X]A[X]A[X]A[X]A[X] and B[X]B[X]B[X]B[X]B[X] are isomorphic as kkkkk-algebras. Does it follow that A≅kBA≅kBA~=_(k)BA \cong_{k} BA≅kB ? In other words, is the kkkkk-algebra AAAAA cancellative?
A special case of Question 1, famously known as the Zariski Cancellation Problem, asks whether affine spaces are cancellative, i.e., whether any polynomial ring in nnnnn variables over a field kkkkk is cancellative. More precisely:
Question 1'. Suppose that BBBBB is an affine kkkkk algebra satisfying B[X]≅kk[X1,…,Xn+1]B[X]≅kkX1,…,Xn+1B[X]~=_(k)k[X_(1),dots,X_(n+1)]B[X] \cong_{k} k\left[X_{1}, \ldots, X_{n+1}\right]B[X]≅kk[X1,…,Xn+1] for some positive integer nnnnn. Does it follow that B≅kk[X1,…,Xn]B≅kkX1,…,XnB~=_(k)k[X_(1),dots,X_(n)]B \cong_{k} k\left[X_{1}, \ldots, X_{n}\right]B≅kk[X1,…,Xn] ? In other words, is the polynomial ring k[X1,…,Xn]kX1,…,Xnk[X_(1),dots,X_(n)]k\left[X_{1}, \ldots, X_{n}\right]k[X1,…,Xn] cancellative?
Abhyankar, Eakin, and Heinzer have shown that any domain AAAAA of transcendence degree one over any field kkkkk is cancellative [3]. In fact, they showed that, for any UFD RRRRR, the polynomial ring R[X]R[X]R[X]R[X]R[X] is cancellative over RRRRR. This was further generalized by Hamann to a ring RRRRR which either contains QQQ\mathbb{Q}Q or is a seminormal domain [52].
In 1972, Hochster demonstrated the first counterexample to Question 1 [53]. His example, a four-dimensional ring over the field of real numbers RRR\mathbb{R}R, is based on the fact that the projective module defined by the tangent bundle over the real sphere with coordinate ring S=R[X,Y,Z]/(X2+Y2+Z2−1)S=R[X,Y,Z]/X2+Y2+Z2−1S=R[X,Y,Z]//(X^(2)+Y^(2)+Z^(2)-1)S=\mathbb{R}[X, Y, Z] /\left(X^{2}+Y^{2}+Z^{2}-1\right)S=R[X,Y,Z]/(X2+Y2+Z2−1) is stably free but not a free SSSSS-module.
One of the major breakthroughs in 1970s was the establishment of an affirmative answer to Question 1' for the case n=2n=2n=2n=2n=2. This was proved over a field of characteristic zero by Fujita, Miyanishi, and Sugie [43,70] and over perfect fields of arbitrary characteristic by Russell [74]. Later, it has been shown that even the hypothesis of perfect field can be dropped [20]. A simplified proof of the cancellation property of k[X,Y]k[X,Y]k[X,Y]k[X, Y]k[X,Y] for an algebraically closed field kkkkk is given by Crachiola and Makar-Limanov in [22].
Around 1989, Danielewski [26] constructed explicit two-dimensional affine domains over the field of complex numbers CCC\mathbb{C}C which are not cancellative over CCC\mathbb{C}C. New examples of noncancellative varieties over any field kkkkk have been studied in [9,32,49][9,32,49][9,32,49][9,32,49][9,32,49]. This addresses the Cancellation Problem, as formulated in Question 1, for all dimensions.
In [45] and [47], the author settled the Zariski Cancellation Problem (Question 1') completely for affine spaces in positive characteristic. She has first shown in [45] that a certain threefold constructed by Asanuma is a counterexample to the ZCP in positive characteristic for the affine three space. Later in [46], she studied a general threefold of the form xmy=F(x,z,t)xmy=F(x,z,t)x^(m)y=F(x,z,t)x^{m} y=F(x, z, t)xmy=F(x,z,t), which includes the Asanuma threefold as well as the famous Russell cubic defined below. A major theorem of [46] is stated as Theorem 5.4 of this article. In [47], using a modification of the theory developed in [46], she constructed a family of examples which are counterexamples to the ZCP in positive characteristic in all dimensions greater than 2 . The ZCP is still a challenging problem in characteristic zero. A few candidate counterexamples are discussed below.
The Russell cubic. Let A=C[X,Y,Z,T]/(X2Y+X+Z2+T3),V=SpecAA=C[X,Y,Z,T]/X2Y+X+Z2+T3,V=Specâ¡AA=C[X,Y,Z,T]//(X^(2)Y+X+Z^(2)+T^(3)),V=Spec AA=\mathbb{C}[X, Y, Z, T] /\left(X^{2} Y+X+Z^{2}+T^{3}\right), V=\operatorname{Spec} AA=C[X,Y,Z,T]/(X2Y+X+Z2+T3),V=Specâ¡A and let xxxxx denote the image of XXXXX in AAAAA. The ring AAAAA, known as the Russell cubic, is one of the simplest examples of the Koras-Russell threefolds, a family of threefolds which arose in the context of the problem of determining whether there exist nonlinearizable C∗C∗C^(**)\mathbb{C}^{*}C∗-actions on C3C3C^(3)\mathbb{C}^{3}C3. It was an exciting open problem for some time whether A≅C[3]A≅C[3]A~=C^([3])A \cong \mathbb{C}^{[3]}A≅C[3]. It was first observed that the ring AAAAA (respectively the variety VVVVV ) has several properties in common with C[3]C[3]C^([3])\mathbb{C}^{[3]}C[3] (respectively C3C3C^(3)\mathbb{C}^{3}C3 ), for instance,
(i) AAAAA is a regular UFD.
(ii) There exists an injective CCC\mathbb{C}C-algebra homomorphism from AAAAA to C[3]C[3]C^([3])\mathbb{C}^{[3]}C[3]. Note that C[3]↪AC[3]↪AC^([3])↪A\mathbb{C}^{[3]} \hookrightarrow AC[3]↪A.
(iii) The variety VVVVV is homeomorphic (in fact, diffeomorphic) to R6R6R^(6)\mathbb{R}^{6}R6.
(iv) VVquad V\quad VV has logarithmic Kodaira dimension −∞−∞-oo-\infty−∞.
These properties appeared to provide evidence in favor of the surmise that A≅C[3]A≅C[3]A~=C^([3])A \cong \mathbb{C}^{[3]}A≅C[3]. The establishment of an isomorphism between AAAAA and C[3]C[3]C^([3])\mathbb{C}^{[3]}C[3] would have led to counterexamples to the "Linearization Conjecture" on C3C3C^(3)\mathbb{C}^{3}C3 (stated in [58]) and the Abhyankar-Sathaye Conjecture for n=3n=3n=3n=3n=3 (stated in Section 5 of the present article). Indeed, if AAAAA were isomorphic to C[3]C[3]C^([3])\mathbb{C}^{[3]}C[3], as was then suspected, it would have shown the existence of nonlinearizable C∗C∗C^(**)\mathbb{C}^{*}C∗-actions on C3C3C^(3)\mathbb{C}^{3}C3. Moreover, note that
(v) A/(x−λ)=C[2]A/(x−λ)=C[2]A//(x-lambda)=C^([2])A /(x-\lambda)=\mathbb{C}^{[2]}A/(x−λ)=C[2] for every λ∈C∗λ∈C∗lambda inC^(**)\lambda \in \mathbb{C}^{*}λ∈C∗.
Therefore, if AAAAA were isomorphic to C[3]C[3]C^([3])\mathbb{C}^{[3]}C[3], then property (vi) would show that x−λx−λx-lambdax-\lambdax−λ cannot be a coordinate in AAAAA for any λλlambda\lambdaλ and then, by property (v), it would have yielded a counterexample to the Abhyankar-Sathaye Conjecture for n=3n=3n=3n=3n=3.
However, Makar-Limanov proved [65] that A≠C[3]A≠C[3]A!=C^([3])A \neq \mathbb{C}^{[3]}A≠C[3]; for this result, he introduced a new invariant which distinguished between AAAAA and C[3]C[3]C^([3])\mathbb{C}^{[3]}C[3]. This invariant, which he had named AK-invariant, is now named Makar-Limanov invariant and is denoted by ML. It is defined in Section 3. Makar-Limanov proved that
However, the Makar-Limanov invariant of C[n]C[n]C^([n])\mathbb{C}^{[n]}C[n] is CCC\mathbb{C}C for any integer n≥1n≥1n >= 1n \geq 1n≥1. Thus A⊈C[3]A⊈C[3]A⊈C^([3])A \nsubseteq \mathbb{C}^{[3]}A⊈C[3]. Subsequently, other Koras-Russell threefolds were shown to be not isomorphic to the polynomial ring. Eventually, Kaliman-Koras-Makar-Limanov-Russell proved that every C∗C∗C^(**)\mathbb{C}^{*}C∗-action on C3C3C^(3)\mathbb{C}^{3}C3 is linearizable (cf. [55]).
Now for ZCP in characteristic zero, a crucial question, still open, is whether A[1]=C[4]A[1]=C[4]A^([1])=C^([4])A^{[1]}=\mathbb{C}^{[4]}A[1]=C[4]. Because if A[1]=C[4]A[1]=C[4]A^([1])=C^([4])A^{[1]}=\mathbb{C}^{[4]}A[1]=C[4], then AAAAA would be a counterexample to the ZCP in characteristic zero for n=3n=3n=3n=3n=3. In this context, the following results have been proved:
(ix) VVquad V\quad VV is A1A1A^(1)\mathbb{A}^{1}A1-contractible (Dubouloz-Fasel [31], also see [33,54]).
Note that A[1]=C[4]A[1]=C[4]A^([1])=C^([4])A^{[1]}=\mathbb{C}^{[4]}A[1]=C[4] would imply that ML(A[1])=CMLâ¡A[1]=CML(A^([1]))=C\operatorname{ML}\left(A^{[1]}\right)=\mathbb{C}MLâ¡(A[1])=C and Dubouloz's result (viii) shows that the latter indeed holds. On the other hand, Asok had suggested a program for showing that the variety VVVVV is not A1A1A^(1)\mathbb{A}^{1}A1-contractible and hence AAA\mathrm{A}A is not a stably polynomial
ring (see [54]). However, Hoyois, Krishna, and Østvær have proved [54] that a step in his program does not hold for VVVVV. They had further shown that VVVVV is stably A1A1A^(1)\mathbb{A}^{1}A1-contractible. In a remarkable paper [31], Dubouloz and Fasel have established that VVVVV is in fact A1A1A^(1)\mathbb{A}^{1}A1-contractible, which seems to provide further evidence in favor of A[1]=C[4]A[1]=C[4]A^([1])=C^([4])A^{[1]}=\mathbb{C}^{[4]}A[1]=C[4]. The variety VVVVV is in fact the first example of an A1A1A^(1)\mathbb{A}^{1}A1-contractible threefold which is not algebraically isomorphic to C3C3C^(3)\mathbb{C}^{3}C3.
Nonrectifiable epimorphisms and Asanuma's rings. Let m≤nm≤nm <= nm \leq nm≤n be two integers. A kkkkk-algebra epimorphism ϕ:k[X1,…,Xn]→k[Y1,…,Ym]Ï•:kX1,…,Xn→kY1,…,Ymphi:k[X_(1),dots,X_(n)]rarr k[Y_(1),dots,Y_(m)]\phi: k\left[X_{1}, \ldots, X_{n}\right] \rightarrow k\left[Y_{1}, \ldots, Y_{m}\right]Ï•:k[X1,…,Xn]→k[Y1,…,Ym] is said to be rectifiable if there exists a kkkkk-algebra automorphism ψψpsi\psiψ of k[X1,…,Xn]kX1,…,Xnk[X_(1),dots,X_(n)]k\left[X_{1}, \ldots, X_{n}\right]k[X1,…,Xn] such that ϕ∘ψ(Xi)=Yiϕ∘ψXi=Yiphi_(@)psi(X_(i))=Y_(i)\phi_{\circ} \psi\left(X_{i}\right)=Y_{i}ϕ∘ψ(Xi)=Yi for 1≤i≤m1≤i≤m1 <= i <= m1 \leq i \leq m1≤i≤m and ϕ∘ψ(Xj)=0ϕ∘ψXj=0phi_(@)psi(X_(j))=0\phi_{\circ} \psi\left(X_{j}\right)=0ϕ∘ψ(Xj)=0 for m+1≤j≤nm+1≤j≤nm+1 <= j <= nm+1 \leq j \leq nm+1≤j≤n. Equivalently, over an algebraically closed field kkkkk, a kkkkk embedding Φ:Akm↪AknΦ:Akm↪AknPhi:A_(k)^(m)↪A_(k)^(n)\Phi: \mathbb{A}_{k}^{m} \hookrightarrow \mathbb{A}_{k}^{n}Φ:Akm↪Akn is said to be rectifiable if there exists an automorphism ΨΨPsi\PsiΨ of AknAknA_(k)^(n)\mathbb{A}_{k}^{n}Akn such that Ψ∘ΦΨ∘ΦPsi_(@)Phi\Psi_{\circ} \PhiΨ∘Φ is the canonical embedding mapping (y1,…,ym)→(y1,…,ym,0,…,0)y1,…,ym→y1,…,ym,0,…,0(y_(1),dots,y_(m))rarr(y_(1),dots,y_(m),0,dots,0)\left(y_{1}, \ldots, y_{m}\right) \rightarrow\left(y_{1}, \ldots, y_{m}, 0, \ldots, 0\right)(y1,…,ym)→(y1,…,ym,0,…,0).
A famous theorem of Abhyankar-Moh and Suzuki proves that any epimorphism ϕ:k[X,Y]→k[T]Ï•:k[X,Y]→k[T]phi:k[X,Y]rarr k[T]\phi: k[X, Y] \rightarrow k[T]Ï•:k[X,Y]→k[T] is rectifiable in characteristic zero [5,86]. On the other hand, in positive characteristic, there exist nonrectifiable epimorphisms from k[X,Y]k[X,Y]k[X,Y]k[X, Y]k[X,Y] to k[T]k[T]k[T]k[T]k[T] (see Segre [83], Nagata [71]). It is an open problem whether there exist nonrectifiable epimorphisms over the field of complex numbers (see [38]).
Asanuma has described an explicit method for constructing affine rings which are stably polynomial rings, by making use of nonrectifiable epimorphisms ([7], also see [38, PROPOSITION 3.7]). Such rings are considered to be potential candidates for counterexamples to the ZCP. For instance, when kkkkk is of positive characteristic, nonrectifiable epimorphisms from k[X,Y]k[X,Y]k[X,Y]k[X, Y]k[X,Y] to k[T]k[T]k[T]k[T]k[T] yield counterexamples to the ZCP.
Let ϕ:R[X,Y,Z]→R[T]Ï•:R[X,Y,Z]→R[T]phi:R[X,Y,Z]rarrR[T]\phi: \mathbb{R}[X, Y, Z] \rightarrow \mathbb{R}[T]Ï•:R[X,Y,Z]→R[T] be defined by
Shastri constructed the above epimorphism ϕÏ•phi\phiÏ• and proved that it defines a nonrectifiable (polynomial) embedding of the trefoil knot in AR3AR3A_(R)^(3)\mathbb{A}_{\mathbb{R}}^{3}AR3 [84]. Using a result of Serre [63, tHEoREM 1, P. 281], one knows that ker(ϕ)=(f,g)kerâ¡(Ï•)=(f,g)ker(phi)=(f,g)\operatorname{ker}(\phi)=(f, g)kerâ¡(Ï•)=(f,g) for some f,g∈k[X,Y,Z]f,g∈k[X,Y,Z]f,g in k[X,Y,Z]f, g \in k[X, Y, Z]f,g∈k[X,Y,Z]. Using fffff and ggggg, Asanuma constructed the ring B=R[T][X,Y,Z,U,V]/(TdU−f,TdV−g)B=R[T][X,Y,Z,U,V]/TdU−f,TdV−gB=R[T][X,Y,Z,U,V]//(T^(d)U-f,T^(d)V-g)B=\mathbb{R}[T][X, Y, Z, U, V] /\left(T^{d} U-f, T^{d} V-g\right)B=R[T][X,Y,Z,U,V]/(TdU−f,TdV−g) and proved that B[1]=R[T][4]=R[5](cfB[1]=R[T][4]=R[5](cfB^([1])=R[T]^([4])=R^([5])(cfB^{[1]}=\mathbb{R}[T]^{[4]}=\mathbb{R}^{[5]}(\mathrm{cf}B[1]=R[T][4]=R[5](cf. [7, cORoLLARY 4.2]). He asked [7, REMARK 7.8]:
Question 2. Is B=R[4]B=R[4]B=R^([4])B=\mathbb{R}^{[4]}B=R[4] ?
The interesting aspect of the question is that once the problem gets solved, irrespective of whether the answer is "Yes" or "No," that is, either way, one would have solved a major problem in Affine Algebraic Geometry. Indeed:
If B=R[4]B=R[4]B=R^([4])B=\mathbb{R}^{[4]}B=R[4], then there exist nonlinearizable R∗R∗R^(**)\mathbb{R}^{*}R∗-actions on the affine four-space AR4AR4A_(R)^(4)\mathbb{A}_{\mathbb{R}}^{4}AR4.
If B≠R[4]B≠R[4]B!=R^([4])B \neq \mathbb{R}^{[4]}B≠R[4], then clearly BBBBB is a counterexample to the ZCP!!
3. CHARACTERIZATION PROBLEM
The Characterization Problem in affine algebraic geometry seeks a "useful characterization" of the polynomial ring or, equivalently (when the ground field is algebraically
closed), an affine nnnnn-space. For instance, the following two results give respectively an algebraic and a topological characterization of k[1]k[1]k^([1])k^{[1]}k[1] (or AC1AC1A_(C)^(1)\mathbb{A}_{\mathbb{C}}^{1}AC1 ).
Theorem 3.1. Let kkkkk be an algebraically closed field of characteristic zero. Then the polynomial ring k[1]k[1]k^([1])k^{[1]}k[1] is the only one-dimensional affine UFD with A∗=k∗A∗=k∗A^(**)=k^(**)A^{*}=k^{*}A∗=k∗.
Theorem 3.2. Let kkkkk be the field of complex numbers CCC\mathbb{C}C. Then the affine line AC1AC1A_(C)^(1)\mathbb{A}_{\mathbb{C}}^{1}AC1 is the only acyclic normal curve.
While the Characterization Problem is one of the most important problems in affine algebraic geometry in its own right, it is also closely related to some of the challenging open problems on the affine space like the "Cancellation Problem." For instance, each of the above characterizations of k[1]k[1]k^([1])k^{[1]}k[1] immediately solves the Cancellation Problem in dimension one: A[1]=k[2]⟹A=k[1]A[1]=k[2]⟹A=k[1]A^([1])=k^([2])Longrightarrow A=k^([1])A^{[1]}=k^{[2]} \Longrightarrow A=k^{[1]}A[1]=k[2]⟹A=k[1]. The complexity of the Characterization Problem increases with the dimension of the rings.
In his attempt to solve the Cancellation Problem for the affine plane, Ramanujam obtained a remarkable topological characterization of the affine plane C2C2C^(2)\mathbb{C}^{2}C2 in 1971 [72]. He proved that
Theorem 3.3. C2C2C^(2)\mathbb{C}^{2}C2 is the only contractible smooth surface which is simply connected at infinity.
Ramanujam also constructed contractible surfaces which are not isomorphic to C2C2C^(2)\mathbb{C}^{2}C2. Soon, in 1975, Miyanishi [67] obtained an algebraic characterization of the polynomial ring k[2]k[2]k^([2])k^{[2]}k[2]. He proved that
Theorem 3.4. Let kkkkk be an algebraically closed field of characteristic zero and AAAAA be a twodimensional affine factorial domain over kkkkk. Then A=k[2]A=k[2]A=k^([2])A=k^{[2]}A=k[2] if and only if it satisfies the following:
(ii) There exists an element f∈Af∈Af in Af \in Af∈A and a subring BBBBB of AAAAA such that A[f−1]=Af−1=A[f^(-1)]=A\left[f^{-1}\right]=A[f−1]=B[f−1][1]Bf−1[1]B[f^(-1)]^([1])B\left[f^{-1}\right]^{[1]}B[f−1][1].
This algebraic characterization was used by Fujita, Miyanishi, and Sugie [43,70] to solve the Cancellation Problem for k[X,Y]k[X,Y]k[X,Y]k[X, Y]k[X,Y]. In 2002 [50], using methods of Mumford and Ramanujam, Gurjar gave a topological proof of the cancellation property of C[X,Y]C[X,Y]C[X,Y]\mathbb{C}[X, Y]C[X,Y].
Remarkable characterizations of the affine three space were obtained by Miyanishi [68] and Kaliman [56] (also see [69] for a beautiful survey). We state below the version of Kaliman.
Theorem 3.5. Let A be a three-dimensional smooth factorial affine domain over the field of complex numbers CCC\mathbb{C}C. Let X=SpecAX=Specâ¡AX=Spec AX=\operatorname{Spec} AX=Specâ¡A. Then A=C[3]A=C[3]A=C^([3])A=\mathbb{C}^{[3]}A=C[3] if and only if it satisfies the following:
(ii) H3(X,Z)=0H3(X,Z)=0H_(3)(X,Z)=0H_{3}(X, \mathbb{Z})=0H3(X,Z)=0, or XXXXX is contractible.
(iii) XXXXX contains a cylinder-like open set VVVVV such that V≅U×A2V≅U×A2V~=U xxA^(2)V \cong U \times \mathbb{A}^{2}V≅U×A2 for some curve UUUUU and each irreducible component of the complement X∖VX∖VX\\VX \backslash VX∖V has at most isolated singularities.
When A[1]=C[4]A[1]=C[4]A^([1])=C^([4])A^{[1]}=\mathbb{C}^{[4]}A[1]=C[4], it is easy to see that AAAAA possesses properties (i) and (ii) of Theorem 3.5. Thus, by Theorem 3.5 , the ZCP for C[3]C[3]C^([3])\mathbb{C}^{[3]}C[3] reduces to examining whether condition (iii) necessarily holds for a CCC\mathbb{C}C-algebra AAAAA satisfying A[1]=C[4]A[1]=C[4]A^([1])=C^([4])A^{[1]}=\mathbb{C}^{[4]}A[1]=C[4].
In [29], we have obtained another characterization of the affine three-space using certain invariants of an affine domain defined by locally nilpotent derivations. We state it below.
Locally nilpotent derivations and a characterization of C[3]C[3]C^([3])\mathbb{C}^{[3]}C[3]. Let BBBBB be an affine domain over a field kkkkk of characteristic zero. A kkkkk-linear derivation DDDDD on BBBBB is said to be a locally nilpotent derivation if, for any a∈Ba∈Ba in Ba \in Ba∈B there exists an integer nnnnn (depending on aaaaa ) satisfying Dn(a)=0Dn(a)=0D^(n)(a)=0D^{n}(a)=0Dn(a)=0. Let LND(B)LNDâ¡(B)LND(B)\operatorname{LND}(B)LNDâ¡(B) denote the set of all locally nilpotent kkkkk-derivations of BBBBB and let
LND∗(B)={D∈LND(B)∣Ds=1 for some s∈B}LND∗â¡(B)={D∈LNDâ¡(B)∣Ds=1 for some s∈B}LND^(**)(B)={D in LND(B)∣Ds=1" for some "s in B}\operatorname{LND}^{*}(B)=\{D \in \operatorname{LND}(B) \mid D s=1 \text { for some } s \in B\}LND∗â¡(B)={D∈LNDâ¡(B)∣Ds=1 for some s∈B}
Then we define
ML(B):=⋂D∈LND(B)kerD and ML∗(B):=⋂D∈LND∗(B)kerDMLâ¡(B):=â‹‚D∈LNDâ¡(B) kerâ¡D and ML∗â¡(B):=â‹‚D∈LND∗â¡(B) kerâ¡DML(B):=nnn_(D in LND(B))ker D quad" and "quadML^(**)(B):=nnn_(D inLND^(**)(B))ker D\operatorname{ML}(B):=\bigcap_{D \in \operatorname{LND}(B)} \operatorname{ker} D \quad \text { and } \quad \operatorname{ML}^{*}(B):=\bigcap_{D \in \operatorname{LND}^{*}(B)} \operatorname{ker} DMLâ¡(B):=â‹‚D∈LNDâ¡(B)kerâ¡D and ML∗â¡(B):=â‹‚D∈LND∗â¡(B)kerâ¡D
The above ML(B)MLâ¡(B)ML(B)\operatorname{ML}(B)MLâ¡(B), introduced by Makar-Limanov, is now called the Makar-Limanov invariant of BBBBB; ML* ∗(B)∗(B)^(**)(B){ }^{*}(B)∗(B) was introduced by Freudenburg in [41, P. 237]. We call it the MakarLimanov-Freudenburg invariant or ML-F invariant. If LND∗(B)=∅LND∗â¡(B)=∅LND^(**)(B)=O/\operatorname{LND}^{*}(B)=\emptysetLND∗â¡(B)=∅, we define ML∗(B)ML∗(B)ML^(**)(B)\mathrm{ML}^{*}(B)ML∗(B) to be BBBBB. We have obtained the following theorem [29, THEOREM 4.6].
Theorem 3.6. Let A be a three-dimensional affine factorial domain over an algebraically closed field kkkkk of characteristic zero. Then the following are equivalent:
(I) A=k[3]A=k[3]A=k^([3])A=k^{[3]}A=k[3].
(II) ML∗(A)=kML∗â¡(A)=kML^(**)(A)=k\operatorname{ML}^{*}(A)=kML∗â¡(A)=k.
(III) ML(A)=kMLâ¡(A)=kML(A)=k\operatorname{ML}(A)=kMLâ¡(A)=k and ML∗(A)≠AML∗â¡(A)≠AML^(**)(A)!=A\operatorname{ML}^{*}(A) \neq AML∗â¡(A)≠A.
A similar result has also been proved in dimension two under weaker hypotheses [29, theorem 3.8]. The above characterization of the affine three-space does not extend to higher dimensions [29, EXAMPLE 5.6]. So far, no suitable characterization of the affine nnnnn-space for n≥4n≥4n >= 4n \geq 4n≥4 is known to the author.
4. AFFINE FIBRATIONS
Let RRRRR be a commutative ring. A fundamental theorem of Bass-Connell-Wright and Suslin [10,85][10,85][10,85][10,85][10,85] on the structure of locally polynomial algebras states that:
Theorem 4.1. Let AAAAA be a finitely presented algebra over a ring R. Suppose that for each maximal ideal mmmmm of R,Am=Rm[n]R,Am=Rm[n]R,A_(m)=R_(m)^([n])R, A_{m}=R_{m}^{[n]}R,Am=Rm[n] for some integer n≥0n≥0n >= 0n \geq 0n≥0. Then A≅SymR(P)A≅SymRâ¡(P)A~=Sym_(R)(P)A \cong \operatorname{Sym}_{R}(P)A≅SymRâ¡(P) for some finitely generated projective RRRRR-module PPPPP of rank nnnnn.
Now for a prime ideal PPPPP of RRRRR, let k(P)k(P)k(P)k(P)k(P) denote the residue field RP/PRPRP/PRPR_(P)//PR_(P)R_{P} / P R_{P}RP/PRP. The area of affine fibrations seeks to derive information about the structure and properties of an RRRRR-algebra AAAAA from the information about the fiber rings A⊗Rk(P)(=AP/PAP)A⊗Rk(P)=AP/PAPAox_(R)k(P)(=A_(P)//PA_(P))A \otimes_{R} k(P)\left(=A_{P} / P A_{P}\right)A⊗Rk(P)(=AP/PAP) of AAAAA at the points PPPPP of the prime spectrum of RRRRR, i.e., at the prime ideals PPPPP of RRRRR.
An RRRRR-algebra AAAAA is said to be an AnAnA^(n)\mathbb{A}^{n}An-fibration over RRRRR if AAAAA is a finitely generated flat RRRRR-algebra and for each prime ideal PPPPP of R,A⊗Rk(P)=k(P)[n]R,A⊗Rk(P)=k(P)[n]R,Aox_(R)k(P)=k(P)^([n])R, A \otimes_{R} k(P)=k(P)^{[n]}R,A⊗Rk(P)=k(P)[n].
The most important problem on AnAnA^(n)\mathbb{A}^{n}An-fibrations, due to VeÇsfeÇler and DolgaÄev [87], can be formulated as follows:
Question 3. Let RRRRR be a Noetherian domain of dimension ddddd and AAAAA be an AnAnA^(n)\mathbb{A}^{n}An-fibration over RRRRR.
(i) If RRRRR is regular, is A≅SymR(Q)A≅SymRâ¡(Q)A~=Sym_(R)(Q)A \cong \operatorname{Sym}_{R}(Q)A≅SymRâ¡(Q) for some projective module QQQQQ over RRRRR ? (In particular, if RRRRR is regular local, is then A=R[n]A=R[n]A=R^([n])A=R^{[n]}A=R[n] ?)
(ii) In general, what can one say about the structure of AAAAA ?
Question 3 is considered a hard problem. When n=1n=1n=1n=1n=1, it has an affirmative answer for all ddddd. This has been established in the works of Kambayashi, Miyanishi, and Wright [59,60]. Their results were further refined by Dutta who showed that it is enough to assume the fiber conditions only on generic and codimension-one fibers ([34]; also see [14, 17, 40]).
In case n=2,d=1n=2,d=1n=2,d=1n=2, d=1n=2,d=1, and RRRRR contains the field of rational numbers, an important theorem of Sathaye [81] gives an affirmative answer to Question 3 (i). To prove this theorem, Sathaye first generalized the Abhyankar-Moh expansion techniques originally developed over k[[x]]k[[x]]k[[x]]k[[x]]k[[x]] to k[[x1,…,xn]]kx1,…,xnk[[x_(1),dots,x_(n)]]k\left[\left[x_{1}, \ldots, x_{n}\right]\right]k[[x1,…,xn]] [80]. The expansion techniques were used by Abhyankar-Moh to prove their famous epimorphism theorem. The generalized expansion techniques were further developed by Sathaye [82] to prove a conjecture of Daigle and Freudenburg. The result was a crucial step in Daigle-Freudenburg's theorem that the kernel of any triangular derivation of k[X1,X2,X3,X4]kX1,X2,X3,X4k[X_(1),X_(2),X_(3),X_(4)]k\left[X_{1}, X_{2}, X_{3}, X_{4}\right]k[X1,X2,X3,X4] is a finitely generated kkkkk-algebra [23].
When the residue field of RRRRR is of positive characteristic, Asanuma has shown in [6, THEOREM 5.1] that Question 3 (i) has a negative answer for n=2,d=1n=2,d=1n=2,d=1n=2, d=1n=2,d=1, and the author has generalized Asanuma's ring [47] to give a negative answer to Question 3 (i) for n=2n=2n=2n=2n=2 and any d>1d>1d > 1d>1d>1 (also see [48]). In Theorem 5.4, the author proved that in a special situation A2A2A^(2)\mathbb{A}^{2}A2-fibration is indeed trivial.
However, if n=2,d=2n=2,d=2n=2,d=2n=2, d=2n=2,d=2, and RRRRR contains the field of rational numbers, Question 3 (i) is an open problem. A candidate counterexample is discussed in Section 7.
In the context of Question 3 (ii), a deep work of Asanuma [6] provides a stable structure theorem for AAAAA. As a consequence of Asanuma's structure theorem, it follows that if RRRRR is regular local, then there exists an integer m≥0m≥0m >= 0m \geq 0m≥0 such that A[m]=R[m+n]A[m]=R[m+n]A^([m])=R^([m+n])A^{[m]}=R^{[m+n]}A[m]=R[m+n]. Thus it is very tempting to look for possible counterexamples to the affine fibration problem in order to
obtain possible counterexamples to the ZCP in characteristic zero. One can see [12,24,36,37][12,24,36,37][12,24,36,37][12,24,36,37][12,24,36,37] and [38, SECTION 3.1] for more results on affine fibrations.
So far we have considered affine fibrations where the fibre rings are polynomial rings. Bhatwadekar and Dutta have obtained some nice results on rings whose fiber rings are of the form k[X,1/X][15,16]k[X,1/X][15,16]k[X,1//X][15,16]k[X, 1 / X][15,16]k[X,1/X][15,16]. Later Bhatwadekar, the author, and A. Abhyankar studied rings whose fiber rings are Laurent polynomial algebras or rings of the form k[X,1/f(X)]k[X,1/f(X)]k[X,1//f(X)]k[X, 1 / f(X)]k[X,1/f(X)], or of the form k[X,Y,1/(aX+b),1/(cY+d)]k[X,Y,1/(aX+b),1/(cY+d)]k[X,Y,1//(aX+b),1//(cY+d)]k[X, Y, 1 /(a X+b), 1 /(c Y+d)]k[X,Y,1/(aX+b),1/(cY+d)] for some a,b,c,d∈k[1,2,18,19,44]a,b,c,d∈k[1,2,18,19,44]a,b,c,d in k[1,2,18,19,44]a, b, c, d \in k[1,2,18,19,44]a,b,c,d∈k[1,2,18,19,44]. One of the results of Bhatwadekar and the author provides a Laurent polynomial analogue of Theorem 4.1 and the affine fibration problem Question 3. More generally, we have [19, THEOREMS A AND C]:
Theorem 4.2. Let RRRRR be a Noetherian normal domain with field of fractions KKKKK and AAAAA be a faithfully flat RRRR